题意：输入一个长度为n的序列a，满足1<=ai<=i，要求确定每个数的正负号，使得所有数的总和为0。

思路：贪心部分的理论依据：前i个数可以凑出1～sum[i]的所有整数。

        数学归纳，n=1时成立，假设n=k之前所有项都成立，当n=k+1时。sum[k+1]=sum[k]+a[k+1]。

        只需证明能凑出sum[k]+1~sum[k+1]间的整数即可。设1≤p≤a[k+1]，sum[k]+p=sum[k]+a[k+1]-(a[k+1]-p)。

        因为1≤a[i]≤i，易得sum[k]≥k,a[k+1]-p≤k。又因为已知前k个数可以凑出1~sum[k]，所以一定可以凑出a[k+1]-p。

        所以只需从之前凑出sum[k]里面剪掉凑出a[k+1]-p的数就可以凑出sum[k]+p。所以从1~sum[k+1]都可以凑出。

        知道这个之后就很容易了，首先判断sum和是否是偶数，其次排序依次遍历即可。

1 #include
     
        2 #include
      
        3 #include
       
         4 using namespace std; 5  6 const int maxn = 1e5 + 5; 7  8 struct node 9 {10     int x;11     int id;12 }a[maxn];13 14 int ans[maxn];15 16 bool cmp(node a, node b)17 {18     return a.x > b.x;19 }20 21 int main()22 {23     int n;24     while (cin >> n)25     {26         long long sum = 0;27         for (int i = 0; i < n; i++)28         {29             cin >> a[i].x;30             a[i].id = i;31             sum += a[i].x;32         }33         if (sum % 2)34         {35             cout << "No" << endl;36             continue;37         }38         sum /= 2;39         sort(a, a + n, cmp);40         for (int i = 0; i < n; i++)41         {42             if (a[i].x <= sum)43             {44                 ans[a[i].id] = 1;45                 sum -= a[i].x;46             }47             else ans[a[i].id] = -1;48         }49         cout << "Yes" << endl;50         for (int i = 0; i < n-1; i++)51             cout << ans[i] << " ";52         cout << ans[n - 1] << endl;53     }54     return 0;55 }