本文共 1553 字，大约阅读时间需要 5 分钟。
题意：给你一个数列 b，其中bi 为 ai 的数字和，ai是一个单调递增的序列，问你求出 an 最小的那个可能的序列
解题思路： an 最小其实也就是使得 ai 最小 ，ai最小就是枚举 前k 位都和 a[i-1] 相等，在 第k-1位的时候 大于 a[i-1]即可。
解题代码：
1 // File Name: 509.cpp 2 // Author: darkdream 3 // Created Time: 2015年03月24日 星期二 10时01分03秒 4 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 #include 23 #include 24 #define LL long long25 #define maxn 30526 using namespace std;27 int a[305];28 int ans[405];29 int sum[405];30 int tmp[405];31 int ok(int k ,int n)32 {33 if(k == 0)34 return 1;35 int tl = k /9 ; 36 int tt= (k % 9 ==0 ?0:1);37 if(tl + tt -1 <= n)38 {39 for(int i = 0 ;i = 0 ;i --)50 {51 sum[i] = sum[i+1]+ ans[i];52 }53 for(int i = 0 ;i <= 400 ;i ++)54 {55 int t = k - sum[i+1] ;56 if(ans[i] == 9 || t <= ans[i])57 continue;58 for(int j = ans[i] + 1; j <= 9 ;j ++)59 {60 memset(tmp,0,sizeof(tmp));61 if(ok(t-j,i-1))62 {63 for(int s = i +1;s <= 400; s ++)64 tmp[s] = ans[s];65 tmp[i] = j; 66 return ;67 }68 }69 }70 }71 int main(){72 int n ;73 scanf("%d",&n);74 for(int i = 1;i <= n;i ++)75 {76 scanf("%d",&a[i]);77 solve(a[i]) ; 78 int j;79 for(j = 400; j>= 0 ;j --)80 {81 if(tmp[j] != 0)82 break;83 }84 for(;j >= 0 ;j --)85 printf("%d",tmp[j]);86 printf("\n");87 memcpy(ans,tmp,sizeof(tmp));88 }89 return 0;90 }
转载于:https://www.cnblogs.com/zyue/p/4362185.html
