自动搬运

查看原文

来自洛谷，原作者为

	droplet ** 看着两百多行的代码行行都有错，这使你充满了决心　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　*

搬运于2025-08-24 22:47:16，当前版本为作者最后更新于2025-03-29 21:34:26，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一篇用 double 的做法

分析题面

$0\le m,n\le 2\times 10^3$，可以看出我们可以枚举两边的车，对于每两辆车判断是否在隧道。此时需要用 $O(1)$ 或 $O(\log n)$ 的复杂度判断是否在隧道。

判断是否在隧道

首先我们需要得知两车相遇位置，由于隧道具有单调性（因为互不重叠），所以可以二分求出相遇位置是否在隧道。

下面是求 $i$，$j$ 两车相遇位置 $met$ 的方法：

• 后出发的出发后两车共走路程 $dis=s+c_{i}+d{j}-2 \times\max\{c_{i},d_{j}\}$
• 从左侧（苏黎世）出发车走的路程（即相遇位置）$met=\max\{c_{i},d_{j}\}-c_{i}+\frac{dis}{2}$
• 整理得 $met=\frac{s+d_{j}-c_{i}}{2}$

此时二分三个区间①②③（二为隧道）。

• 当车在区间②时，返回撞车。
• 当车在区间①时，向右二分。
• 当车在区间③时，向左二分。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int s,t,m,n,x[N],y[N],a[N],b[N];

bool work(int i,int j){
	int l=1,r=t,mid;
	double met=(s+b[j]-a[i])/2.0;
	while(l<=r){
		mid=(l+r)>>1;
		if(x[mid]<met&&met<y[mid]) return 1;
		if(y[mid]<=met) l=mid+1;
		else r=mid-1;
	}
	return 0;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>s>>t>>m>>n;
	for(int i=1;i<=t;i++) cin>>x[i];
	for(int i=1;i<=t;i++) cin>>y[i];
	for(int i=1;i<=m;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			if(work(i,j)){
				cout<<"YES";
				return 0;
			}
		}
	}
	cout<<"NO";
	return 0;
}