社区讨论
两种思路,一种AC,一种WA+RE,求助!
P1007独木桥参与者 5已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @m3vj7zik
- 此快照首次捕获于
- 2024/11/24 19:44 去年
- 此快照最后确认于
- 2025/11/04 13:59 4 个月前
这道题目我的思路就是直接模拟,遍历每一个人,在一个人移动过后在它对应的位置打上标记(标记这个人对应的索引加1,后续方便查找),在后面如果遇到其他人的位置和这个标记过的点重合,则二者掉头,之前那个标记的人回头走两步,新人回头走一步(转头不费时间)。但最终有Re(不知道什么原因)还有WA。
CPP#include <iostream>
#include <string.h>
#define ll long long
using namespace std;
const int MAXN=100000;
int L,N;
ll visited[100000]={0};//此数组用来标记走过的点
typedef struct p{
ll po;
ll tag=1;//方向-1或1,1向右走,-1向左走。
}p;
p ps[MAXN];int pslen=0;
int main(){
cin>>L>>N;
for (int i=0;i<N;i++){
p p1;
cin>>p1.po;
ps[pslen++]=p1;
}
ll x1=0,x2=MAXN;
//对于求最小值,只需要让离桥头小于L的一半的向桥头走,其余向桥尾走。
//找出在左半边离桥头最远的点和右半边离桥尾最短的点。
for (int i=0;i<N;i++){
if (ps[i].po<=L/2){
x1=max(x1,ps[i].po);
}
else {
x2=min(x2,ps[i].po);
}
}
int ans1=max(x1,L+1-x2);//计算最小时间
//最大时间这样模拟:在左半边的人都往右走,右半边的人都往左走。
for (int i=0;i<N;i++){
if (ps[i].po>L/2){
ps[i].tag=-1;
}
}
int nu=0;//代表已经通过桥的人数
ll maxT=0;//代表最长时间
while (nu!=N){
maxT++;
cout<<"nu:"<<nu<<endl;
for (int i=0;i<N;i++){
if (ps[i].tag==0) continue;//tag==0代表这个人已经通过了
if (visited[ps[i].po]>0) {
ll x=ps[i].po;
ps[i].tag=-ps[i].tag;//调转方向
ps[visited[ps[i].po]-1].tag=-ps[visited[ps[i].po]-1].tag;//前一个人调转反向
ps[visited[ps[i].po]-1].po+=ps[visited[ps[i].po]-1].tag*2;//前一个人回头走两步
visited[ps[visited[ps[i].po]-1].po]=visited[ps[i].po];//前一个人走两步后的位置打上标记,标记仍为索引+1
ps[i].po+=ps[i].tag*1;
visited[ps[i].po]=i+1;//将现在这个人走过的点打上标记
visited[x]=0;//将原来的标记取消
continue;
}
ps[i].po=ps[i].po+ps[i].tag*1;
if (ps[i].po<=0||ps[i].po>=L+1){
nu++;ps[i].tag=0;
continue;//通过
}
visited[ps[i].po]=i+1;//打上标记,标记索引+1
}
memset(visited,0,MAXN*sizeof(int));//每一次循环都将数组重置一遍,因为位置会变
}
cout<<ans1<<" "<<maxT<<endl;
return 0;
}
后来参考题解,发现掉头并不影响结果,重新写出代码成功AC。但是当我将这串代码和我上面的代码进行随机数对拍时结果都是一致的,不知道是什么原因QAQ。。。
回复
共 5 条回复,欢迎继续交流。
正在加载回复...