题意：n个数分别为a[i]，问是否存在一组对应的b[i]，b[i]=1 || b[i]=-1，使得ai*bi的n项和为0。
题解：
先证明一个结论吧，对于1≤ai≤i+1，前面ai个数一定可以凑出1~sum[i]中的任意一个数.
对于i=1显然成立，假设对于i=k结论成立，那么对于i=k+1来说，只要证明sum[k]+i，1≤i≤ak+1可以凑出来就行了。
因为sum[k]+i≥k+1，且1≤ak+1≤k+1，所以可以先选一个ak+1，剩下的0≤sum[k]+i-ak+1≤sum[k]一定是可以由前面的数字凑出来的。
这就证明了贪心的正确性。
转自：http://www.cnblogs.com/jerryRey/p/4702658.html
代码中这个cmp也可以换成
用结构体存id,val 再写两个cmp排序就好了。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 1e5+;
int a[maxn];
int r[maxn];
int n;
long long sum;
bool cmp(int x,int y) //这个cmp的思想要会
{
return a[x]<a[y];
}
void init()
{
sum=;
memset(a,,sizeof(a));
memset(r,,sizeof(r));
}
int main()
{
freopen("hell.in","r",stdin);
freopen("hell.out","w",stdout);
while(scanf("%d",&n)!=EOF)
{
init();
for(int i=;i<n;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
r[i]=i;
}
sort(r,r+n,cmp);
if(sum%==)
puts("No");
else
{
puts("Yes");
sum>>=;
//cout<<sum<<endl;
for(int i=n-;i>=;i--)
{
if(a[r[i]]<=sum)
{
sum-=a[r[i]];
a[r[i]]=;
}
else
a[r[i]]=-; //注意这里改变的是a数组不是r数组
}
for(int i=;i<n-;i++)
printf("%d ",a[i]);
printf("%d\n",a[n-]);
}
}
return ;
}