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 複製多行