社区讨论

请教各位大神一个问题qwq

P8481 「HGOI-1」Binary search参与者 4已保存回复 9

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
9 条
当前快照
1 份
快照标识符
@lo88amx6
此快照首次捕获于
2023/10/27 14:24
2 年前
此快照最后确认于
2023/10/27 14:24
2 年前
查看原帖
这道题一开始想贪心写,后面自己发现了样例2这种情况,后面就用bfs想暴力直接ac,但写完发现subtask3的第二点wa了,就只wa了这一个,然后就疯狂debug把自己心态搞崩了呜呜呜
CPP
#include<stdio.h>
#include<string.h>
const unsigned long long MAX=1e10;
int n,arr[1050000],q,arr1[100000000];
unsigned long long list[54000004],list1[54000004],ans;
int judge(){
	for(unsigned long long i=1;i<=list[0];i++){
		unsigned long long beg=list[i]/MAX,end=list[i]%MAX;
	//	printf("%llu %llu\n",beg,end);
		if(beg==end){
			return 1;
		}	
	}
	return 0;//没找到答案,还需要找 
}

void bfs(int n1){
	for(unsigned long long i=1;i<=list[0];i++){
		unsigned long long  beg=list[i]/MAX,end=list[i]%MAX;
		//printf("%llu %d %d\n",list[i],beg,end);
		if((beg+end)%2==1){
			 unsigned long long mid=(beg+end)/2;
			if(arr[mid]>n1){
				list1[++list1[0]]=(beg)*MAX+mid;
				list1[++list1[0]]=(beg)*MAX+mid+1; 
			}
			else if(arr[mid+1]<n1){
				list1[++list1[0]]=(mid)*MAX+end;
				list1[++list1[0]]=(mid+1)*MAX+end; 
			}
			else if(arr[mid]==n1){
				list1[++list1[0]]=(beg)*MAX+mid;
				list1[++list1[0]] =(mid)*MAX+end; 
			}
			else if(arr[mid+1]==n1){
				list1[++list1[0]]=(beg)*MAX+mid+1;
				list1[++list1[0]] =(mid+1)*MAX+end; 
			}
		} 
		else{
			unsigned long long mid=(beg+end)/2;
			if(arr[mid]>n1){//要找的数还在左边;
			list1[++list1[0]]=beg*MAX+mid;
			list1[++list1[0]]=beg*MAX+mid-1; 
			}
			else if(arr[mid]<n1){
				list1[++list1[0]]=(mid)*MAX+end;
				list1[++list1[0]]=(mid+1)*MAX+end; 
			}
			else{
				list1[++list1[0]]=(mid)*MAX+end;
				list1[++list1[0]]=(beg)*MAX+mid; 
			}
		}
	}
	//memcpy(list,list1,sizeof(unsigned long long)*(list1[0]+3));
	for(unsigned long long i=0;i<=list1[0];i++){
		list[i]=list1[i];
	}
	list1[0]=0;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&arr[i]);
	}
	scanf("%d",&q);
	
	for(int i=1;i<=q;i++){
		ans=0;
		list[0]=1;list[1]=1*MAX+n;
		
		int remain1=0;
		scanf("%d",&remain1);
		if(remain1<1e8){
			if(!arr1[remain1]){
				while(!judge()){
			ans++;
			bfs(remain1);
		}
		arr1[remain1]=ans;
		printf("%llu\n",ans);
			}
			else{
				printf("%llu\n",arr1[remain1]);
			}
		}
		else{
		
		while(!judge()){
			ans++;
			bfs(remain1);
		}
	
		printf("%llu\n",ans);}
	}
	return 0;
}

一开始的bfs写的还十分简洁,后面各种怀疑出问题就打“补丁”写的有点乱了,各位大神救救本蒟蒻吗呜呜....

回复

9 条回复,欢迎继续交流。

正在加载回复...