本文主要是介绍codeforces 289 C Sums of Digits，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
贪心，做了两个半小时没做出来！主要在于求有k位且恰比某个数大的最小值，从左到右检查可以加1的位，若后面的位满足条件，再根据solve中的方法满足条件的最小值。
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#define inf 10000000
#define pi acos(-1.0)
#define eps 1e-8
#define seed 131
using namespace std;
typedef pair<int,int> pii;
typedef unsigned long long ULL;
typedef long long LL;
const int maxn=100005;
int n;
int b[305];
int a[305][1000];
void solve(int k,int u,int p)
{int tot=0;for(int i=1;i<=k;i++){a[p][i]=9;tot+=9;}for(int i=1;i<=k;i++){if(i==1&&k!=1){if(tot-u>8){a[p][i]-=8;tot-=8;}else{a[p][i]-=(tot-u);return;}}else{if(tot-u>9){a[p][i]-=9;tot-=9;}else{a[p][i]-=(tot-u);return;}}}
}
bool so(int k,int u,int p)
{int tot=0;for(int i=1;i<=k;i++){a[p][i]=a[p-1][i];tot+=a[p][i];}if(tot<u){for(int i=k;i>=1;i--){if(u-tot>9-a[p][i]){tot+=9-a[p][i];a[p][i]=9;}else{a[p][i]+=u-tot;return true;}}return false;}else if(tot==u){int m=0;for(int i=k;i>=1;i--){if(a[p][i]<9&&m>0){a[p][i]++;int e=0;m--;for(int j=i+1;j<=k;j++){a[p][j]=9;e+=9;}for(int j=i+1;j<=k;j++){if(e-m>9){e-=9;a[p][j]=0;}else{a[p][j]-=(e-m);return true;}}}m+=a[p][i];}return false;}else{int cha=tot-u;cha++;int m=0;for(int i=k;i>=1;i--){if(a[p][i]<9&&m>=cha){a[p][i]++;m-=cha;int e=0;for(int j=i+1;j<=k;j++){a[p][j]=9;e+=9;}for(int j=i+1;j<=k;j++){if(e-m>9){e-=9;a[p][j]=0;}else{a[p][j]-=(e-m);return true;}}}m+=a[p][i];}return false;}
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&b[i]);int wei[305];int k;k=b[1]/9;if(b[1]%9!=0)k++;if(b[1]==0)k=1;solve(k,b[1],1);wei[1]=k;int ans=k;for(int i=2;i<=n;i++){k=b[i]/9;if(b[i]%9!=0)k++;if(k<=ans){k=ans;if(so(k,b[i],i)){wei[i]=k;continue;}else{ans=k+1;solve(ans,b[i],i);wei[i]=ans;}}else{ans=k;solve(ans,b[i],i);wei[i]=ans;}}for(int i=1;i<=n;i++){for(int j=1;j<=wei[i];j++)printf("%d",a[i][j]);printf("\n");}return 0;
}
这篇关于codeforces 289 C Sums of Digits的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
