UVA1614 Hell on the Markets（结论+贪心）
题目链接
1.题目大意：给出一个全正数ai(1<=ai<=i)的序列，现在问能否通过变一部分数为负数使得正数和负数部分相加为0
2.题目实际上可以转化为，能否找到两部分使得它们的和都为sum/2，题目一看有点像动态规划，但是下一章才是dp，因此可能是贪心取，但是测试了几个样例感觉不太对劲，怎么排序都不行，双指针首尾取也不行。没办法了看了题解原来是一个重要结论：
在1<=a[i]<=i时， 前i个数一定可以凑出1~sum[i]的所有整数
证明：
3.有了以上结论，不难知道sum只有是偶数就能找到解，因为能取到sum，因此一定能找到一部分和为sum/2，剩下那一部分肯定也是sum/2,。但是应该如何取呢，有的地方说需要排序贪心取，有的地方说可以直接从后往前取，看了知乎dl的证明：
那么直接从后向前贪心即可
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;
int a[maxn],sg[maxn];
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;
while(cin>>n){
ll sum=0;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
}
if(sum&1){
cout<<"No"<<endl;
continue;
}
sum/=2;
for(int i=n;i>=1;i--){
if(a[i]<=sum){
sum-=a[i];
sg[i]=1;
}else sg[i]=-1;
}
cout<<"Yes"<<endl;
for(int i=1;i<=n;i++){
cout<<sg[i]<<" ";
}
cout<<endl;
}
return 0;
}
reference：知乎