Decrease the Sum of Digits"/>
D. Decrease the Sum of Digits
思路:最开始是从前往后看,然后判当前sum+str[i]和s的情况,比如相等和>,相等还要判后面有没有0再考虑进位。写了一下发现这样十分麻烦。所以转化一下思路。
反正总共位数不超过20个,不如从后面开始每一位去进位,进完位后check一下当前每一位的和加起来是不是满足<=s的。所以预处理一下10进制位,然后模拟一下。
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e5;
typedef long long LL;
LL p10[20],a[20];
char str[22];
LL cal(LL n)
{LL sum=0;for(LL i=1;i<=n;i++) sum+=a[i];return sum;
}
void solve()
{memset(a,0,sizeof(a));memset(str,0,sizeof(str));LL s;cin>>str+1;cin>>s;LL n=strlen(str+1);for(LL i=1;i<=n;i++) a[n-i+1]=str[i]-'0';LL ans=0;LL sum=cal(n);if(sum<=s){cout<<0<<endl;return;}else{//进位 for(LL i=1;i<=n;i++){ans+=(10-a[i])*p10[i];a[i]=0;a[i+1]++;if(cal(n)<=s) break;}cout<<ans<<endl;}
}
int main(void)
{LL t;cin>>t;p10[1]=1;for(LL i=2;i<=20;i++) p10[i]=p10[i-1]*10;while(t--){solve();}
return 0;
}
更多推荐
D. Decrease the Sum of Digits
发布评论