UVA 1614 Hell on the Markets 【贪心+结论题】

题目链接

题意

给一串序列，保证序列中每个数满足ai≤i，问能否给这些数每个数前面填上正负号，使得其和为0.

分析

先上结论

数列an满足 ∀ai∈an,ai≤i ，则对于任何正整数S≤sum[i] （sum[i]为前i项和），总能从an中的前i项中选出某些数，使其和为S
即对于每项不大于下标的数列，总能凑出一些数，使其和为1~前缀和中的任意一个数

---

证明：
用数学归纳法
1) 当n=1时显然成立

2)假设当n=k时成立，即任何一个正整数S都可以表示为a1∼an中某些数的和

3)对于n=k+1，1~sum[k]中的数有2）知显然可以凑出。而对于sum[k]+1~sum[k+1]间即sum[k]+t(1≤t≤ak+1)间的整数：

sum[k]+t=sum[k]−(ak+1−t)+ak+1

∵ak+1≤k+1且t≥q⟹ak+1−t≤k
又∵sum[k]≥ak+a1≥k+1
∴0≤sum[k]−(ak+1−t)≤sum[k]
∴sum[k]+t可以用a1∼ak中的任意一些数加上ak+1凑成

得证

---

代码实现也就很简单了，首先所有数的和为奇数是肯定不能一分为二的。然后先排个序，然后从后到前扫一遍能选就选，选到总和的一般为止。不用担心选了某个数以后就凑不齐了，因为有上面的那个结论，总能够凑齐的。

AC代码

//UVA 1614 Hell on the Markets
//AC 2016-7-29 23:12:13
//Greedy, Math Conclusion
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <set>
#include <string>
#include <map>
#include <queue>
#include <deque>
#include <list>
#include <sstream>
#include <stack>
using namespace std;

#define cls(x) memset(x,0,sizeof x)
#define inf(x) memset(x,0x3f,sizeof x)
#define neg(x) memset(x,-1,sizeof x)
#define ninf(x) memset(x,0xc0,sizeof x)
#define st0(x) memset(x,false,sizeof x)
#define st1(x) memset(x,true,sizeof x)
#define INF 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define bug cout<<"here"<<endl;
//#define debug


pair<int,int> num[100100];
bool choose[100100];
int n;
long long sum;

int main()
{
    #ifdef debug
        freopen("E:\Documents\code\input.txt","r",stdin);
        freopen("E:\Documents\code\output1.txt","w",stdout);
    #endif
    while(cin>>n)
    {
        sum=0;
        for(int i=0;i<n;++i)
        {
            cin>>num[i].first;
            num[i].second=i;
            sum+=num[i].first;
        }
        if(sum%2!=0)
        {
            cout<<"No"<<endl;
            continue;
        }
        else
            cout<<"Yes"<<endl;
        sum/=2;
        st0(choose);
        sort(num,num+n);
        for(int i=n-1;i>=0;--i)
        {
            if(sum-num[i].first>=0)
            {
                sum-=num[i].first;
                choose[num[i].second]=1;
            }
        }
        for(int i=0;i<n;++i)
        {
            if(i!=0) cout<<" ";
            if(choose[i]) cout<<1;
            else cout<<-1;
        }
        cout<<endl;
    }
    return 0;
}