1 /*  2 给定<50块砖，不同高度，堆尽可能高尽可能接近高度的两座塔  3 输入文件两行：第一行： 砖数，第二行：砖厚0 砖厚1 ...  4 */  5 #include <stdio.h>  6   7 void sort(int *a,int n)  8 {  9     int i,j,k,temp; 10  11     for(i=0;i<n-1;i++) 12     { 13         k=i; /*给记号赋值*/ 14         for(j=i+1;j<n;j++) 15             if(a[k]>a[j ]) k=j; /*是k总是指向最小元素*/ 16         if(i!=k)/*当k!=i是才交换，否则a[i ] 即为最小*/ 17         { 18             temp=a[i ]; 19             a[i ]=a[k]; 20             a[k]=temp; 21         } 22     } 23 } 24  25 int sum(int *a, int n) 26 { 27     int i; 28     int temp = 0; 29     for (i = 0; i<n; i++) 30     { 31         temp += a[i]; 32     } 33  34     return temp; 35 } 36  37 void main() 38 { 39     int i; 40     int n; 41     int a[50]; 42  43     //freopen("test.txt","r",stdin);    //for debug local 44     scanf("%d", &n); 45     for (i = 0; i<n; i++) 46     { 47         scanf("%d", &a[i]); 48     } 49  50     if (sum(a, n) % 2 != 0) 51         printf("-1"); 52  53     sort(a, n);    //升序排序 54  55     int b[50], c[50]; 56     int len_b = n/2, len_c = n/2; 57     for (i = 0; i<n/2; i++)    //分成两堆尽可能接近的砖 58     { 59         b[i] = a[2*i]; 60         c[i] = a[2*i+1]; 61     } 62     if (n%2 != 0)    //奇数个，最后一个加入b 63     { 64         b[i] = a[n-1]; 65         len_b++; 66     } 67  68     int sum_a, sum_b, diff, temp; 69     int find = 1, j = 0; 70     int abigb = 0;    //1:b>c,0:b<c 71     while(find) 72     { 73         sum_a = sum(b, len_b); 74         sum_b = sum(c, len_c); 75         abigb = (sum_a > sum_b)?1:0; 76         diff = abigb?(sum_a-sum_b):(sum_b-sum_a); 77         find  = 0; 78         if (abigb) 79         { 80             temp = 0; 81             //找到小于diff的最大数 82             for (i = 0; i<len_b; i++) 83             { 84                 if (b[i] < diff && b[i] > temp) 85                 { 86                     temp = b[i]; 87                     j = i; 88                     find  = 1; 89                 } 90             } 91             //找到 92             if (find == 1) 93             { 94                 c[len_c] = b[j];len_c++; 95                 b[j] = b[len_b - 1];len_b--; 96             } 97         } 98         else 99         {100             temp = 0;101             //找到小于diff的最大数102             for (i = 0; i<len_c; i++)103             {104                 if (c[i] < diff && c[i] > temp)105                 {106                     temp = c[i];107                     j = i;108                     find  = 1;109                 }110             }111             //找到112             if (find == 1)113             {114                 b[len_b] = c[j];len_b++;        //搬移最小的115                 c[j] = c[len_c - 1];len_c--;116             }117         }118     }119 120     if (sum_a == sum_b)121         printf("%d", sum_a);122     else123         printf("-1");124 }