当你想到一个char好像能塞下8个flag
查看原帖
当你想到一个char好像能塞下8个flag
1395519
_21_3tzhz楼主2024/7/15 16:48

不是,搞那么麻烦干啥,老老实实弄个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;
}
2024/7/15 16:48
加载中...