1409D. Decrease the Sum of Digits(贪心,构造)

贪心,构造)"/>

1409D. Decrease the Sum of Digits(贪心,构造)

D. Decrease the Sum of Digits

e m m 贪 心 的 想 , 先 把 数 字 n 从 高 位 到 低 位 的 数 位 预 处 理 出 来 emm贪心的想,先把数字n从高位到低位的数位预处理出来 emm贪心的想,先把数字n从高位到低位的数位预处理出来

然 后 从 高 位 看 到 低 位 ( 高 位 能 不 动 就 不 动 的 原 则 ) , 现 在 考 虑 如 何 构 造 最 小 的 数 b 然后从高位看到低位(高位能不动就不动的原则),现在考虑如何构造最小的数b 然后从高位看到低位(高位能不动就不动的原则),现在考虑如何构造最小的数b

设 前 i 位 数 字 和 是 s u m n ( 前 i 位 指 的 是 高 位 到 低 位 ) 设前i位数字和是sumn(前i位指的是高位到低位) 设前i位数字和是sumn(前i位指的是高位到低位)

如 果 s u m n < s , 最 后 结 果 前 i 位 肯 定 不 需 要 变 动 如果sumn<s,最后结果前i位肯定不需要变动 如果sumn<s,最后结果前i位肯定不需要变动

因 为 最 坏 情 况 后 面 数 位 都 变 成 0 , 向 自 己 进 一 位 因为最坏情况后面数位都变成0,向自己进一位 因为最坏情况后面数位都变成0,向自己进一位

s u m n + 1 一 定 小 于 等 于 s , 满 足 条 件 sumn+1一定小于等于s,满足条件 sumn+1一定小于等于s,满足条件

一 旦 s u m n > s , 这 一 位 一 定 要 变 动 , 但 是 不 能 变 大 ( 情 况 更 糟 ) , 只 能 一 直 进 位 变 成 0 一旦sumn>s,这一位一定要变动,但是不能变大(情况更糟),只能一直进位变成0 一旦sumn>s,这一位一定要变动,但是不能变大(情况更糟),只能一直进位变成0

也 就 是 从 这 一 位 开 始 的 位 数 都 变 成 0 , 并 向 前 进 一 位 ( 因 为 后 面 都 是 0 ) 也就是从这一位开始的位数都变成0,并向前进一位(因为后面都是0) 也就是从这一位开始的位数都变成0,并向前进一位(因为后面都是0)

那 么 如 果 s u m n = = s 呢 ? 和 s u m n > s 的 情 况 有 啥 不 同 吗 ? 那么如果sumn==s呢?和sumn>s的情况有啥不同吗? 那么如果sumn==s呢?和sumn>s的情况有啥不同吗?

可 以 说 基 本 没 有 不 同 可以说基本没有不同 可以说基本没有不同

只 不 过 是 说 明 后 面 都 变 成 0 自 己 不 动 可 以 满 足 条 件 s u m n = = s 只不过是说明后面都变成0自己不动可以满足条件sumn==s 只不过是说明后面都变成0自己不动可以满足条件sumn==s

但 是 由 于 只 能 执 行 加 法 的 原 因 , 自 己 不 进 位 , 后 面 数 字 都 变 成 0 ( 是 减 法 ) 但是由于只能执行加法的原因,自己不进位,后面数字都变成0(是减法) 但是由于只能执行加法的原因,自己不进位,后面数字都变成0(是减法)

所 以 和 s u m n > s 的 情 况 是 一 样 的 所以和sumn>s的情况是一样的 所以和sumn>s的情况是一样的

如果后面的数位都等于0自己确实不需要变动,但是这种情况开头特判一下就好了

emm可能讲的比较啰嗦不清楚,一定在评论区提问啊看不懂的话!!

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
int a[22],b[22],s;
signed main()
{int t,n; cin >> t;while( t-- ){cin >> n >> s;int len=0,x=n,sumn=0;memset(a,0,sizeof(a));	memset(b,0,sizeof(b));while( x )a[++len]=x%10,sumn+=a[len],x/=10;//预处理数位和 if( sumn==s ){cout << 0 << endl;continue;}sumn=0;for(int i=len;i>=1;i--)//高位到低位看 {sumn+=a[i];if( sumn<s )//暂时不需要变动 b[i]=a[i];else if( sumn>=s ){b[i+1]++;//向高位进一位 for(int j=i;j>=1;j-- )	b[j]=0;//低位都变成0 break;}	}int now=0;for(int j=1;j<=len;j++)//提取构造的数字 {b[j+1]+=b[j]/10;//啥意思?b[j]可能等于10,那么先向前进位吧...这个无关紧要,我是严谨一点 b[j]%=10;}now=b[len+1];for(int i=len;i>=1;i--)	now=now*10+b[i];cout << now-n << endl;}
}