UVA 1614 - Hell on the Markets 奇怪的股市(贪心,结论)

时间:2021-08-19 09:35:00

先证明一个结论吧,对于1≤ai≤i+1,前面ai个数一定可以凑出1~sum[i]中的任意一个数.

对于i=1显然成立,

假设对于i=k结论成立,那么对于i=k+1来说,只要证明sum[k]+i,1≤i≤ak+1可以凑出来就行了。

因为sum[k]+i≥k+1,且1≤ak+1≤k+1,所以可以先选一个ak+1,剩下的0≤sum[k]+i-ak+1≤sum[k]一定是可以由前面的数字凑出来的。

这就证明了贪心的正确性。

#include<bits/stdc++.h>
using namespace std; const int maxn = 1e5+;
int a[maxn];
int r[maxn];
bool cmp(int x,int y) { return a[x] < a[y]; } int main()
{
int n;
while(~scanf("%d",&n)){
long long sum = ;
for(int i = ; i < n; i++) scanf("%d",a+i),sum += a[i],r[i] = i;
if(sum&) { puts("No"); continue; }
sort(r,r+n,cmp);
sum >>= ;
for(int i = n-; i >= ; i--){
int j = r[i];
if(a[j]<=sum){
sum -= a[j];
a[j] = ;
}else {
a[j] = -;
}
}
printf("Yes\n%d",a[]);
for(int i = ; i < n; i++) printf(" %d",a[i]);
puts("");
}
return ;
}