这道题我苦思冥想了一个小时， 想用背包来揍sum/2， 然后发现数据太大， 空间存不下。
然后我最后还是去看了别人的博客， 发现竟然有个神奇的结论……
幸好我没再钻研， 感觉这个结论我肯定是想不到的……
结论是：在1 <= a[i] <= i时， 前i个数一定可以凑出1~sum[i]的所有整数
证明看这 https://blog.csdn.net/wcr1996/article/details/43957461
其他博客写有了这个结论， 就排序一下， 从大到小， 凑sum/2， 能凑就凑， 最后一定可以凑成。
但是我开始一直想不通为啥这样下去一定可以凑成， 为什么要排序？？其他博客貌似没有
给出解释……
然后我自己思考了挺久， 想通了。
首先这个结论证明一定可以揍成sum/2（sum为奇数不考虑， 输出No）
然后， 从大到小排序。
假设第一个可以凑的数为a[k]， a[k]显然是第一个小于等于sum/2的数
也就是说a[k]之前的数， 也就是所有大于a[k]的数， 都大于sum/2
也就是说这些数不可能来揍sum/2.
然后sum/2就减去了a[k]。那么a[k]之后的数一定可以凑sum/2-a[k]；
为什么呢？这里是关键。
因为要凑sum/2-a[k]的数字肯定小于sum/2-a[k]， 而这些数字一定在a[k]之后
因为a[k]是第一个小于等于sum/2的数， 那么第一个小于等于sum/2-a[k]的数字
肯定小于等于a[k]， 也就肯定在a[k]后面。
所以要凑成sum/2-a[k]的数都在a[k]后面， 这些数字还没有被选到。
因为开始的结论说明肯定可以凑sum/2-a[k]， 而所有需要来凑
sum/2-a[k]的数还没有遍历到。
所以， sum/2-a[k]一定可以用还没遍历到的数凑成。
以此类推， 一直做下去， 肯定可以凑完
over！！！！！！！！！！
#include<cstdio>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
const int MAXN = 112345;
int a[MAXN], id[MAXN], n;
bool cmp(int x, int y)
{
return a[x] > a[y];
}
int main()
{
while(~scanf("%d", &n))
{
long long sum = 0;
REP(i, 0, n)
{
scanf("%d", &a[i]);
sum += a[i];
id[i] = i;
}
if(sum & 1) { puts("No"); continue; }
sort(id, id + n, cmp);
sum >>= 1;
REP(i, 0, n)
{
int t = id[i];
if(a[t] <= sum)
{
sum -= a[t];
a[t] = 1;
}
else a[t] = -1;
}
puts("Yes");
REP(i, 0, n) printf("%d ", a[i]);
puts("");
}
return 0;
}