题目大意：给出n个数字，第i个数字的大小满足 1 <= ai <= i，要求确定每个数的正负号，使得所有数的总和为0
解题思路：总和为0，那sum % 2 == 0 接着分析一下，因为和为0，所以sum / 2要能通过这n个数得到，，那就枚举看看能不能得到 从大到小枚举，取当前这个数的个数和（sum/当前这个数）的值的最小值，接着sum减去这个最小值乘于当前值 如果（sum/当前这个数）是取得的最小值，那么分两种情况 一种是能除尽的，那么（sum － 最小值 ＊ 当前这个数）就刚好为0了，也就是sum／2这个数能求得到，符合了 一种是不能除尽的，那么（sum － 最小值 ＊ 当前这个数）就会有剩下，因为是从大到小枚举的，所以剩下的值只能看那些小值能不能相加得到了
;#define maxn 100010int num[maxn], cnt[maxn], cnt2[maxn];int main() {int n;while(scanf(“%d”, &n) == 1) {long long sum = 0;int MAX = 0;for(int i = 1; i <= n; i++)cnt[i] = cnt2[i] = 0;for(int i = 1; i <= n; i++) {scanf(“%d”, &num[i]);sum += num[i];cnt[num[i]]++;MAX = max(MAX, num[i]);}if(sum % 2) {printf(“No\n”);continue;}bool flag = true;sum /= 2;for(int i = MAX; i >= 1 && flag ; i–) {cnt2[i] = min((long long)cnt[i], sum / i);sum -= (long long)cnt2[i] * i;if(sum == 0)flag = false;}if(flag) {printf(“No\n”);continue;}else {printf(“Yes\n”);for(int i = 1; i <= n; i++) {if(i == 1) {if(cnt2[num[i]] > 0) {printf(“1”);cnt2[num[i]]–;}elseprintf(“-1″);}else {if(cnt2[num[i]] > 0) {printf(” 1″);cnt2[num[i]]–;}elseprintf(” -1″);}}printf(“\n”);}}return 0;}
总结失败的原因能够让人越来越谨慎。
