题解 CF1409D 【Decrease the Sum of Digits】

Suuon_Kanderu

2020-09-12 09:53:10

Solution

看到这个题首先可以暴力枚举 $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"; } } ```