Codeforces Round #667 (Div. 3) D. Decrease the Sum of Digits (贪心)

题意:给你一个正整数\(n\),每次可以对\(n\)加一,问最少操作多少次是的\(n\)的所有位数之和不大于\(s\).
题解:\(n\)的某个位置上的数进位,意味这后面的位置都可以被更新为\(0\),所以我们从高位往低位记录一个\(sum\),然后根据情况判断即可.

代码:

int t;

int s;

ll n;

char str[N];

int main() {

    //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	t=read();

	while(t--){

		scanf("%s",str+1);

		s=read();

		int len=strlen(str+1);

		int cnt=0;

		int pos=-1;

		ll n=0;

		for(int i=1;i<=len;++i){

			ll now=str[i]-'0';

			n=n*10+now;

		}

		for(int i=1;i<=len;++i){

			cnt+=str[i]-'0';

			if(str[i]=='9') continue;

			if(cnt<s) pos=i;

		}

		if(cnt<=s){

			puts("0");

			continue;

		}

		if(pos==-1){

			str[1]='1';

			for(int i=2;i<=len+1;++i) str[i]='0';

			ll tmp=0;

			for(int i=1;i<=len+1;++i){

				ll now=str[i]-'0';

				tmp=tmp*10+now;

			}

			printf("%lld\n",tmp-n);

			continue;

		}

		str[pos]++;

		for(int i=pos+1;i<=len;++i) str[i]='0';

		ll tmp=0;

		for(int i=1;i<=len;++i){

			ll now=str[i]-'0';

			tmp=tmp*10+now;

		}

		printf("%lld\n",tmp-n);

	}

    return 0;

}

巴特西

Codeforces Round #667 (Div. 3) D. Decrease the Sum of Digits (贪心)

最新文章

热门文章