贪心部分的理论依据：前i个数可以凑出1～sum[i]的所有整数。
证明：
第二类数学归纳，n=1时成立，假设n=k之前所有项都成立，当n=k+1时。sum[k+1]=sum[k]+a[k+1]。只需证明能凑出sum[k]+1~su m[k+1]间的整数即可。设1≤p≤a[k+1]，sum[k]+p=sum[k]+a[k+1]-(a[k+1]-p)。因为1≤a[i]≤i，易得sum[k] ≥k,a[k+1]-p≤k。所以一定可以凑出a[k+1]-p。所以只需从之前凑出sum[k]里面剪掉凑出a[k+1]-p的数就可以凑出sum[k]+p。所以 从1~sum[k+1]都可以凑出。
输入n个数，第i个数ai满足1≤ai≤i。对每个数添加符号，使和值为0。
排序后从最大的数开始贪心就好。这次用了一些c++不常用的特性写的，一开始缺了个头文件CE了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include<iostream>
#include<algorithm>
#include<iterator>
using namespace std;
const int maxn=100010;
struct q{
int num,id;
friend ostream& operator << (ostream &out,const q& x){
cout<<x.num;
return out;
}
};
q a[maxn];
int main(){
int n;
while(cin>>n){
long long sum=0;
for(int i=0;i<n;++i){
a[i].id=i;
cin>>a[i].num;
sum+=a[i].num;
}
if(sum&1) {cout<<"No\n";continue;}
sum>>=1;
sort(a,a+n,[](q& a,q& b){return a.num>b.num;});
for(int i=0;i<n;++i){
if(a[i].num<=sum){
sum-=a[i].num;
a[i].num=1;
}
else a[i].num=-1;
}
sort(a,a+n,[](q& a,q& b){return a.id<b.id;});
cout<<"Yes\n";
copy(a,a+n,ostream_iterator<q>(cout," "));
cout<<endl;
}
return 0;
}
|
** 本文迁移自我的CSDN博客，格式可能有所偏差。 **