UVa 1614 - Hell on the Markets(贪心)

贪心部分的理论依据:前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博客 ,格式可能有所偏差。