[CF 509C] Sums of Digits

作法：

首先可以把問題化簡成：給定一個數$S$和一個正整數$n$，求出數字和為恰為$S$且比$n$大的最小正整數是多少。考慮將所求的數字和$n$從最高位開始往下比，找到第一位兩個數不同的位置，假設為 $i$ ，那麼就代表在第 $i$ 位之前所求的數字和$n$對應的位置都是一樣的，至於第$i$位和他之後要怎麼放，假設$S$扣掉第$1$位到第$i-1$位的值後剩下的值為$S2$，那麼就代表第$i$位以後一直到個位數的總和要恰好是$S2$，並且還得滿足第$i$位的值$\geq $ $n$ 的第 $i$ 位的值 $+1$ ，當然還有第$i$位以後的數都要介於$0$和$9$之間，因此就可以先列出一個關於$S2$的不等式，不管$S2$太大或是太小都沒辦法在剩下的位子裡面放完需要的數字總和的數。具體來說，假設$n$的第$i$位的值為$x$，並且第$i+1$位一直到個位還有$y$個位子，那麼$S2$就必須滿足$x+1 \leq S2 \leq 9\cdot (y+1)$。並且剩下的問題不難得知只要往個位數的方向放儘量多的$9$就可以了，也就是從個位數開始往左一直放$9$，直到$S2$被用完為止，但記得要注意到如果$S2$太大，也有可能最後要加到第$i$位身上，畢竟他最大還是可以到$9$，不一定只能放$x+1$。最後只要注意到，當兩個數的第一個不一樣的位置越靠近個位的話，算出來的新的值就會越小，所以只要從小到大枚舉$i$，一找到一個解就趕快回傳就可以了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=500+10 ;
 
void print(const string &s)
{
    for(int i=0,j=0;i<maxn;i++) if(s[i]!='0'||j)
        printf("%c",s[i]) , j=1 ;
    printf("\n") ;
}
 
int s0[maxn] ;
inline int gets(int x,int y){return x?s0[y]-s0[x-1]:s0[y] ;}
string solve(string &s,int S)
{
    reverse(s.begin(),s.end()) ;
    for(int i=0;i<maxn;i++) s0[i]=i?s0[i-1]+s[i]-'0':s[i]-'0' ;
    for(int i=0;;i++)
    {
        if(s[i]=='9') continue ;
        if(gets(i,maxn-1)+1>S || gets(i,maxn-1)+9-(s[i]-'0')+9*i<S)
            continue ;
 
        int las=S-(gets(i,maxn-1)+1) ;
        string t ; t.resize(maxn) ;
        for(int j=0;j<maxn;j++) t[j]=(j>=i?s[j]:'0') ;
        t[i]++ ;
        for(int j=0;j<i && las;j++) t[j]=min(9,las)+'0' , las-=min(9,las) ;
        while(las--) t[i]++ ;
        reverse(t.begin(),t.end()) ;
        return t ;
    }
}
 
string s ;
main()
{
    int n ; scanf("%d",&n) ;
    s.resize(maxn) ;
    for(int i=0;i<maxn;i++) s[i]='0' ;
    while(n--)
    {
        int S ; scanf("%d",&S) ;
        s=solve(s,S) ;
        print(s) ;
    }
}