为什么广搜MLE黑一个?
查看原帖
为什么广搜MLE黑一个?
1032391
封禁用户楼主2024/1/19 18:32

90分!
广度优先搜索模板

q.push(初始状态);
while(!q.empty()){
	int m=q.front();
	q.pop();
	for(循环枚举){
	 if(条件表达式){
	 	q.push(合法的变量); 
	 } 
	} 
} 

推出来的队列遍历模板

int m=q.back();//取出队尾控制遍历范围 
while(q.front()!=m){
if(条件表达式){//发现目标进行处理 
表达式; 
q.pop();
}
else q.push(q.front()),q.pop();//否则移至队尾 
后续表达式;//纯粹遍历时 “后续表达式 ”可以不加 
}//由于队尾是while循环终止的条件,所以需单独再枚举出来 
if(条件表达式){
表达式; 
q.pop();
}
else q.push(q.front()),q.pop();	
}

具体思路

    int n,h=0,ant;
	cin>>n;
	for(int i=1;i<=n;i++) q.push(i);//将n个苹果编号入队 
	while(!q.empty()){//当队列为空时,苹果全部取出 
	h++;//天数增加 
	//设置指针i给队伍排名,指针sum模拟将要取走的苹果排名 
	int m=q.back(),i=1,sum=1;
	while(q.front()!=m){//遍历队列 
	 if(i==sum){
	  if(q.front()==n) ant=h;//当编号为n的苹果被取出,记录其在第几天被取出 
	  q.pop(),sum+=3;//模拟取出,指针sum移动 3位更改取走目标 
	}
     else q.push(q.front()),q.pop();
	 i++;
	}
	if(i==sum){//最后枚举原队尾 
	 if(q.front()==n) ant=h;
	  q.pop();
	}
	else q.push(q.front()),q.pop();	
	}
	cout<<h<<' '<<ant;//输出天数和编号为n的苹果在第几天被取出 

全代码

#include<bits/stdc++.h>
using namespace std;
queue<int>q;
int main(){
	int n,h=0,ant;
	cin>>n;
	for(int i=1;i<=n;i++) q.push(i);//将n个苹果编号入队 
	while(!q.empty()){//当队列为空时,苹果全部取出 
	h++;//天数增加 
	int m=q.back(),i=1,sum=1;//取出队尾控制遍历范围 
	while(q.front()!=m){//遍历队列 
	 if(i==sum){
	  if(q.front()==n) ant=h;//发现目标解 
	  q.pop(),sum+=3;
		}
     else q.push(q.front()),q.pop();
	 i++;
	}
	if(i==sum){//最后枚举原队尾 
	 if(q.front()==n) ant=h;
	  q.pop();
	}
	else q.push(q.front()),q.pop();	
	}
	cout<<h<<" "<<ant;//输出天数 
}
2024/1/19 18:32
加载中...