本文共 2000 字，大约阅读时间需要 6 分钟。
题意：a是严格递增数列，bi是ai每一位的和，告诉你b1~bn，问你怎样搞才能让an最小
思路：让ai刚好大于ai-1弄出来的an最小。所以直接模拟贪心，如果当前位和前一个数的当前位一样并且后面还能生成比前一个数大的数，那么就和前一个数保持一致，否则当前位 = 前一个数当前位+ 1，后面的位数按照最小方式排列。如果排到最后每一位都和前面一个数一致，就把剩余的b从最小的一位一直加满9。
代码：
#include #include #include #include #include #include #include #include #include #include #include #include typedef long long ll;using namespace std;const int maxn = 300 + 10;const int MOD = 1e9 + 7;const int INF = 0x3f3f3f3f;int b[maxn], ans[maxn][maxn + 200], cnt[maxn];void solve1(int i){ cnt[i] = 0; while(b[i] > 9){ ans[i][cnt[i]++] = 9; b[i] -= 9; } ans[i][cnt[i]++] = b[i];}int main(){ int n; scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%d", &b[i]); } solve1(1); for(int i = 2; i <= n; i++){ if(b[i] - 9 * cnt[i - 1] > 0){ solve1(i); } else{ if(b[i] <= ans[i - 1][cnt[i - 1] - 1]){ cnt[i] = cnt[i - 1] + 1; ans[i][cnt[i] - 1] = 1; b[i]--; for(int j = 0; j < cnt[i] - 1; j++){ if(b[i] >= 9){ ans[i][j] = 9; b[i] -= 9; } else if(b[i] > 0){ ans[i][j] = b[i]; b[i] = 0; } else ans[i][j] = 0; } } else{ cnt[i] = cnt[i - 1]; for(int j = cnt[i] - 1; j >= 0; j--){ if(j != 0){ if(b[i] - ans[i - 1][j] <= ans[i - 1][j - 1]){ ans[i][j] = ans[i - 1][j] + 1; b[i] -= ans[i][j]; while(ans[i][j] > 9){ b[i] += ans[i][j] - 1; j++; if(j == cnt[i]){ ans[i][j] = 0; cnt[i]++; } ans[i][j]++; } for(int k = 0; k < j; k++){ if(b[i] >= 9){ ans[i][k] = 9; b[i] -= 9; } else if(b[i] > 0){ ans[i][k] = b[i]; b[i] = 0; } else ans[i][k] = 0; } break; } else{ ans[i][j] = ans[i - 1][j]; b[i] -= ans[i][j]; } } else{ ans[i][j] = ans[i - 1][j]; b[i] -= ans[i][j]; } } if(b[i] > 0){ for(int j = 0; j < cnt[i] && b[i] > 0; j++){ if(b[i] > 9 - ans[i][j]){ b[i] -= 9 - ans[i][j]; ans[i][j] = 9; } else{ ans[i][j] += b[i]; b[i] = 0; } } } } } } for(int i = 1; i <= n; i++){ for(int j = cnt[i] - 1; j >= 0; j--) printf("%d", ans[i][j]); printf("\n"); } return 0;}
转载于:https://www.cnblogs.com/KirinSB/p/10395539.html