社区讨论
请教各位大神一个问题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 条回复,欢迎继续交流。
正在加载回复...