不是,搞那么麻烦干啥,老老实实弄个flag数组记录从0到2*10^8之间的每一个值有没有出现过不就好了? 内存限制?挤一挤总能挤下。 flag数组的大小本来应该是200MB,挤挤可以到25MB。 值得注意的是,这段代码作为C++编译的话会超时,而作为C编译会AC.
#include<stdio.h>
#define SIZE 26000000//25MB左右
char flag[SIZE]={0};
int read(int num){//读取第num个flag
int byte=num/8;
int bit=num%8;
int dat=flag[byte];
dat=(dat&(1<<bit));
return dat?1:0;
}
int set(int num)//将第num个flag设为1
int byte=num/8;
int bit=num%8;
flag[byte]=flag[byte]|(1<<bit);
}
int main(){
int arr[10000],i,n,min,max;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&arr[i]);
}
for(i=0;i<n-1;i++){
//求绝对值
int abs=arr[i]-arr[i+1];
if(abs<0){
abs=-abs;
}
//设置flag,把这个绝对值标记为出现过
set(abs);
}
for(i=0;!read(i);i++);
min=i;//找到最小的绝对值
for(i=SIZE-1;!read(i);i--);
max=i;//找到最大的绝对值
//判断最小值和最大值之间有没有没出现过的绝对值
for(i=min;i<=max;i++){
if(read(i)==0){
printf("Not jolly");
return 0;
}
}
//没有没出现过的的话就Jolly了
printf("Jolly");
return 0;
}