699      阿里云  技术社区[云栖]

poj 1350 Cabric Number Problem

这道题目肯定是不难的，但是的的确确有很多小问题很懊恼，其实在比赛中就最怕这种题，因为那个时候大家的心情都是非常紧张的，这种题就是总是WA，就是不知道为什么。。。。。。

题意比较简单：就是输入一个数（各个数位不全相同，且数字的长度为4），将它的各位从大到小排得的数maxnum和各位从小到大排的数minnum相减，反复循环直至值为0或者6147。且如果开头有0那么0不参与排序。

陷阱有2个：1.如果输入的数小于4位或者大于4位都输出No!!如果忽略了这一点就会OLE。

2.最恶心的，就是题目里面没说可能只有1次的情况，应该输出 1 time，而不是 1 times。。。。。。一个“s”的区别

但我WA还另有原因，为了判断是不是一个四位相同的数，应该是smallDigit==bigDigit，我开始只用了smallDigit==n，所以错了一次

另外，我测试过了在题目中明确规定了测试数据结尾的，不用写 ！=EOF ，也能AC

先写了一个程序测试 1000~9999，四位数中按这种算法第一次减得出的最小值：

#include <iostream>
#include <algorithm>

using namespace std;

int smallDigit(int num)
{
	int a[5];
	a[0]=num%10;
	a[1]=num%100/10;
	a[2]=num%1000/100;
	a[3]=num/1000;

	sort(a,a+4);
	return a[0]*1000+a[1]*100+a[2]*10+a[3];
}

int bigDigit(int num)
{
	int a[5];
	a[0]=num%10;
	a[1]=num%100/10;
	a[2]=num%1000/100;
	a[3]=num/1000;

	sort(a,a+4);
	return a[0]+a[1]*10+a[2]*100+a[3]*1000;
}

int main()
{
	int i;
	int small,big;
	int min=99999;
	int tmp;
	for(i=1000;i<=9999;i++)
	{
		small=smallDigit(i);
		big=bigDigit(i);

		if(small==i)
			continue;

		tmp=big-small;

		if(min>tmp)
			min=tmp;
	}

	printf("%d\n",min);

	return 0;
}

999

为什么要看最小值呢？这里是999，这意味着，只有999这一种情况是三位数，其他的必然是4位数，这和输入的情况就一样了，只需要特殊考虑结果为999的情况即可（网上有牛人用简短的代码实现了判断位数的代码，我附在后面，但是这样时间效率和空间效率就降低了。。。）

AC的代码：

#include <iostream>
#include <algorithm>

using namespace std;

int smallDigit(int num)
{
	int a[5];
	a[0]=num%10;
	a[1]=num%100/10;
	a[2]=num%1000/100;
	a[3]=num/1000;

	sort(a,a+4);
	return a[0]*1000+a[1]*100+a[2]*10+a[3];
}

int bigDigit(int num)
{
	int a[5];
	a[0]=num%10;
	a[1]=num%100/10;
	a[2]=num%1000/100;
	a[3]=num/1000;

	sort(a,a+4);
	return a[0]+a[1]*10+a[2]*100+a[3]*1000;
}

int main()
{
	int n;
	int big,small,result;
	int count;
	while(scanf("%d",&n)!=EOF && n!=-1)
	{
		printf("N=%d:\n",n);

		if(n<1000 || n>9999 || smallDigit(n)==bigDigit(n))
		{
			printf("No!!\n");
			continue;
		}

		result=n;
		count=0;
		do
		{
			small=smallDigit(result);
			big=bigDigit(result);
			result=big-small;
			printf("%d-%d=%d\n",big,small,result);
			count++;
		}while(result!=999 && result!=6174);

		if(result==999)
		{
			count++;
			printf("999-999=0\n");
		}

		printf("Ok!! %d time",count);
		if(count>=2)
			printf("s");
		printf("\n");
	}

	return 0;
}

另外附上别人的代码，在get函数中用up实现位数计算:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int a[5],up;
bool get(int x){
    memset(a,-1,sizeof(a));
    up=0;
    while(x){
        a[up++]=x%10;
        x/=10;
    }
    for(int i=1;i<up;i++)
        if(a[i]!=a[0]) return 1;
    return 0;
}
int main(){
    int n;
    while(cin>>n){
        if(n<0) return 0;
        cout<<"N="<<n<<':'<<endl;
        if(n>9999||n<1000||!get(n)) cout<<"No!!"<<endl;
        else{
            int cnt=0;
            while(n&&n!=6174){
                get(n);
                sort(a,a+up);
                int x=0,y=0;
                for(int i=0;i<up;i++) x=x*10+a[i];
                for(int i=up-1;i>=0;i--) y=y*10+a[i];
                cout<<y<<"-"<<x<<"="<<y-x<<endl;
                n=y-x;
                cnt++;
            }
            cout<<"Ok!! "<<cnt<<" time";
            if(cnt>=2) cout<<"s";
            cout<<endl;
        }
    }
}

而我的是memory：132K，time：0MS

最后更新：2017-04-03 14:53:58

  上一篇： Java中IOUtils

  下一篇： VIM 复制多行