ZOJ 3336 Friend Number II

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3780

题目大意：

给你一个正整数x，要求每个数字上的总和和x相同且比x大的最小整数。

如x=12 答案为21 x=10 答案为100

思路：

因为要比x大的最小，我们很自然的想到个位-1十位+1不就可以了。但是要注意如果是0的话，0-1变为9那么是不行的！而9+1的话变为0也是不行的。

最个位开始查找，找第一个不为0的数-1（不为0的下标为not_zero），在not_zero往高位找到第一个不为9的个数+1，（这样保证了比x大）然后在9+1的这里往后排个序保证最小。

为什么要排序？如x=520那么按照上面的就会变为610 而答案应该为601

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN=1024;

char s[MAXN];

int main()

{

	int T;

	scanf("%d",&T);

	while(T--)

	{

		s[0]='0';

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

		int len=strlen(s);

		int not_zero=len-1;

		while(s[not_zero]=='0')

			not_zero--;

		s[not_zero]--;

		int not_nine=not_zero-1;

		while(s[not_nine]=='9')

			not_nine--;

		s[not_nine]++;

		sort(s+not_nine+1,s+len);

		if(s[0]=='0')

			printf("%s\n",s+1);

		else

			printf("%s\n",s);

	}

	return 0;

}

巴特西

ZOJ 3336 Friend Number II

最新文章

热门文章