自动搬运

查看原文

来自洛谷，原作者为

	Math_rad_round 旋转卡壳有2^4种读法，你知道吗？||NOIP退役苕皮

搬运于2025-08-24 22:22:23，当前版本为作者最后更新于2020-06-14 10:17:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P6607

题意简述

一条长为$L$的线上有$N$个点。每个点都以每秒移动一个单位的速度向前，

当迎面碰到另一个点时，立即掉头并继续向前。确定每个点离开绳子所用时间。

$N\leq 10^5$，所有点的位置和初始方向按位置升序给出

这种“ 相遇掉头并继续向前 ”问题，你可以假装你拿着望远镜在远处看

当你看到两个点相遇时，因为你区分不出每一个点，所以你只是会以为两个点 穿 了过去

例如原本有两个点$\ \ \ \ \ \ \ \ \ \ \ \$ $A(3)$右，$B(4)$左

相遇时过了$0.5$秒，此时$\ \$ $A(3.5)$右，$B(3.5)$左

掉头，$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ 此时$\ \$ $A(3.5)$左，$B(3.5)$右

再过$0.5$秒，$\ \ \ \ \ \ \ \$此时$\ \$ $A(3)$左，$B(4)$右

如果把$A,B$反转，$$ 就是$\ \$ $B(3)$左，$A(4)$右

而如果直接穿过——$\ \ \ \ \ \ \ \ \ \$ $B(3)$左，$A(4)$右

所以如果有$A(3)$右，那$10$秒后一定有一个点$(13)$右

同时，因为不可能互相穿过，所以每个点的顺序一定不会改

比如$A$一开始在$B$左边紧邻，那$A$永远都在$B$左边紧邻

所以我们只要处理出

左边有点到达的时间，从小到大配对给左边的若干个点，

右边有点到达的时间，从大到小配对给接下来的点，

AC代码：

#include<iostream>
using namespace std;
int a[100001];
int b[100001]; 
int c[100001];
int main(){
	int n,l;
	cin>>n>>l;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		cin>>b[i];
	}
	int h=0;
	for(int i=1;i<=n;i++){
		if(b[i]==0){//左边到达 
			cout<<a[i]<<" ";
		}
	}
	for(int i=1;i<=n;i++){
		if(b[i]==1){//右边到达 
			cout<<l-a[i]<<" ";
		}
	}
}

谢谢观赏！