贪心枚举,代码里的注释很详细
C. Sums of Digits
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Vasya had astrictly increasingsequence of positive integersa1, …,an. Vasya used it to build a new sequenceb1, …,bn, wherebiis the sum of digits ofai’s decimal representation. Then sequenceaigot lost and all that remained is sequencebi.
Vasya wonders what the numbersaicould be like. Of all the possible options he likes the one sequence with the minimum possible last numberan. Help Vasya restore the initial sequence.
It is guaranteed that such a sequence always exists.
Input
The first line contains a single integer numbern(1≤n≤300).
Nextnlines contain integer numbersb1, …,bn— the required sums of digits. Allbibelong to the range1≤bi≤300.
Output
Printninteger numbers, one per line— the correct option for numbersai, in order of following in sequence. The sequence should be strictly increasing. The sum of digits of thei-th number should be equal tobi.
If there are multiple sequences with least possible numberan, print any of them. Print the numbers without leading zeroes.
Sample test(s)
input
3123
output
123
input
3321
output
311100
/* ***********************************************Author:CKbossCreated Time :2015年02月06日 星期五 15时31分06秒File Name:CF509C.cpp************************************************ */#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <string>#include <cmath>#include <cstdlib>#include <vector>#include <queue>#include <set>#include <map>using namespace std;int n;int b[333];int pos[333];int num[333][500];int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",b+i);pos[0]=1; /// 第一个数 贪心int temp=b[1];if(temp==0) num[1][pos[1]++]=0;while(temp>0){if(temp>=9) { temp-=9; num[1][pos[1]++]=9; }else { num[1][pos[1]++]=temp; temp=0; }}/// 剩下的数 贪心for(int i=2;i<=n;i++){int lastsum=b[i-1];/// 上一位的已经确定的数字和bool flag=false;for(int j=0;flag==false;j++) /// 枚举位置{if(j-1>=0) lastsum-=num[i-1][j-1];///枚举所在的位加多少for(int k=num[i-1][j]+1;k<=9&&flag==false;k++){int add = k-num[i-1][j];/// 剩下的数的范围可以在 0 ~ 9*j 之间if(j-1>=0){if(lastsum+add<=b[i]&&lastsum+add+9*j>=b[i]) /// 成功{flag=true;pos[i]=max(j+1,pos[i-1]);/// 贪心部分的值 valint val = b[i]-lastsum-add;int tn=0;while(val>0){if(val>=9) { val-=9; num[i][tn++]=9; }else { num[i][tn++]=val; val=0; }}/// 枚举的那一位num[i][j]=k;/// 如果存在的不变部分for(int kk=j+1;kk<pos[i-1];kk++){num[i][kk]=num[i-1][kk];}}}else /// 在j==0时特殊考虑{if(lastsum+add==b[i]) /// 成功{flag=true;pos[i]=pos[i-1];for(int kk=0;kk<pos[i];kk++){num[i][kk]=num[i-1][kk];}num[i][j]=k;}}}}}for(int i=1;i<=n;i++){for(int j=pos[i]-1;j>=0;j–)printf("%d",num[i][j]); putchar(10);}return 0;}
，变幻原是永恒，我们唯有用永恒的诺言制约世事的变幻。
