题解 CF1409D 【Decrease the Sum of Digits】

题意：

给定n,求一个最小的x，使n+x的各位数之和小于等于s。

解法

加着加着各位数之和变小了，我们就想到了进位。

我们就可以：从低位一位一位往高位进位，直到满足条件为止。

原因:

• 低位进位需要的代价远比高位进位需要的代价小。
• 假设本来高位加一次需要 10^k ，如果从低位往上进位的话，就用了 <10^k 的代价，而且还让各位数之和更少。

应该是很好理解的。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
unsigned long long n,ans,r;
int t,s,tot;
int main(){
    scanf("%d",&t);
    for(int i=1;i<=t;i++){
        scanf("%lld%d",&n,&s);
        tot=ans=0;
        r=n;
        while(r){
            tot+=r%10;
            r/=10;
        }//求出n的各位数之和
        if(tot<=s){
            printf("0\n");
            continue;
        }//一开始n的各位数之和就小于等于s
        for(unsigned long long res=1;tot>s&&res<n;res*=10){
            int c=n/res%10;
            if(c==0) continue;
            ans+=(10-c)*res;
            n+=(10-c)*res;
            tot=0;
            r=n;
            while(r){
                tot+=r%10;
                r/=10;
            }//求各位数之和
        }//模拟从低位往高位进位
        printf("%lld\n",ans);
    }
    return 0;
}