UVA1614 Hell on the Markets（结论+贪心）

题目链接

---

1.题目大意：给出一个全正数a_i(1<=a_i<=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：知乎