题解 CF1409D 【Decrease the Sum of Digits】
Suuon_Kanderu
2020-09-12 09:53:10
看到这个题首先可以暴力枚举 $k$,不过复杂度感人。
显然只有在进位时才会减小 $n$,所以我们只要枚举能够使 $n$ 进位的数就 ok 了。
- 枚举时这样枚举,假设 $n = 12345$,我们枚举 $k = 10 - 5 = 5~,~k = 10^2 - 45 = 55 ~,~k = 10^3-345 = 655 ~,~k = 10^4 - 2345 = 7655 ~,~ k = 10^5 - 12345 = 67655$ 。
- 显然,$k$ 单调递增,所以说如果满足条件直接输出。
- 注意特判 $n$ 的数码和已经比 $s$ 小的情况。
- 还有就是使用 `unsigned long long`。因为可能会爆 `long long`。
```
#include<bits/stdc++.h>
typedef unsigned long long ll;
ll digit(ll k) {// 获得一个数的数码
ll cnt = 0;
while(k)cnt += k % 10 ,k /= 10;
return cnt;
}
ll work(ll n , ll s) {
if(digit(n) <= s)return 0;
ll k = 1 , cnt = 0 , t = n;
while(t)cnt++ , t /= 10;
for(ll i = 1; i <= cnt; i++) {
k *= 10;
if(digit(k - n % k + n) <= s)
return k - n%k;
}
}
int main() {
int t = 0;
scanf("%d" , &t);
while(t--) {
ll n , s;
std::cin >> n >> s;
std::cout << work(n , s) << "\n";
}
}
```