求解一个ACM题,不知道自己错在哪
题目描述:
Description
Recently Ginger found that there are many numbers, digits of whom can be rearranged to a consecutive sequence. For instance, 254310 is a consecutive-digit number, since the digits of it are 2, 5, 4, 3, 1 and 0, which can be rearranged to “0, 1, 2, 3, 4, 5”.
A sequence is consecutive, if it forms a one-ascending digit sequence either consecutively or circularly from 9 to 0. For example, both “1, 2, 3, 4” and “8, 9, 0, 1” are consecutive sequences.
In a consecutive-digit number, each digit (0~9) can only appear once.
Input
There are several input cases, a single positive integer in a single line for each input case.
Input end with 0.
Output
YES or NO in a single line, if the given number is a consecutive-digit number or not.
Sample Input
1423
7980
21350
2100
0
Sample Output
YES
YES
NO
NO
大意是说输入一个整数,每个数位重新排列后是一个连续的序列,如输入254130,重排后为012345。9~0是循环的,如8901。
输入的每个数由0~9构成,每个数字只能出现一次。
我的算法如下:
是首先获取每个数位,保存在数组 b[]里,然后对b[]排序,判断是否有重复的数字出现;
否则,再判断数组 b[] 的第一位和最后一位是否分别等于0和9,如果是,在数组c[10]={0,1,2,3,4,5,6,7,8,9}里扣掉数组b[]里的元素,然后如果数组c[]里剩下的元素是连续的,则 b[] 是连续的;
否则,判断b[i]-b[i-1]是否等于1,如果是,则b[]是连续的。
代码如下:
#include <iostream>
#include <cstdlib> //qsort
using namespace std;
int comp(const void *a, const void *b)
{
return (*(int*)a - *(int*)b);
}
int main()
{
int n,i,j,len;
int a[10];
for(i=0; i<10; ++i)
a[i]=0;
while(cin>>n,n)//1423
{
int c[10]={0,1,2,3,4,5,6,7,8,9};
int res=1;
for(i=0; n!=0 && i<10; ++i)
{
a[i] = n % 10;
n /= 10;
}
len = i;//4
int b[len];
for(i=0; i<len; ++i)
b[i]=a[i];
qsort(b, len, sizeof(int), comp);
for(i=1; i<len; ++i)//i=1,2,3
{
if(b[i]==b[i-1])
{
res=0;
break;
}
}
if(res!=0)
{
if(b[0]==0 && b[len-1]==9)
{
for(i=0; i<len; ++i)
{
for(j=i; j<10; ++j)
{
if(c[j]==b[i]) {c[j]=-1; break;}
}
}
qsort(c, 10, sizeof(int), comp);
/*
for(i=0; i<10; ++i)
cout<<c[i]<<" ";
cout<<endl;
*/
for(i=len+1; i<10; ++i)//i=5
{
if((c[i]-c[i-1])!=1) {res=0; break;}
}
}
else
{
for(i=1; i<len; ++i)//i=1,2,3
if((b[i]-b[i-1])!=1) {res=0; break;}
}
}
if(res==1) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
我自己测了几组数据没有问题,但是提交上去就错了。不知道错在哪儿……
[解决办法]
题目没说输入数据在int32以内吧
[解决办法]
做1个试试:
#include <iostream>
#include <queue>
using namespace std;
int func(unsigned long long x);
int main()
{
queue<int> result;
const char* maps[2] = {"NO", "YES"};
unsigned long long input;
cin >> input;
while (cin && input != 0)
{
result.push(func(input));
cin >> input;
}
cout << endl;
while (!result.empty())
{
cout << maps[result.front()] << endl;
result.pop();
}
return 0;
}
int func(unsigned long long x)
{
int count[20] = {0}; //用于存放每位数字的统计,20是为了构造一个循环,便于判断
int mod;
int degree = 0; //位数
do
{
mod = x % 10;
x /= 10;
++count[mod];
++count[mod+10];
++degree;
}while (x > 0);
count[0] = 0; //设置1个标志
//从数组中间的0开始往左扫描第一个计数为0的位置
int pos = 10;
while (count[pos] > 0) pos--;
//往右扫描第一个计数>0的位置
while (count[pos] == 0) pos++;
for (int i = 0; i < degree; i++)
{
if (count[pos+i] != 1)
return 0;
}
return 1;
}