自动搬运

查看原文

来自洛谷，原作者为

	wylnh 漫山遍野你的脸庞，唯有遗忘是最漫长

搬运于2025-08-24 22:52:08，当前版本为作者最后更新于2023-11-12 22:37:01，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

做法：模拟+贪心

题意：在一条长为 $n$ 的路上，有两人分别位于 $p_1,p_2$，速度分别为 $v_1,v_2$ ，求最少多长时间两人走完整条路，即每个位置至少有一人经过。

思路：

• 容易发现走完全程共有三种情况：
  • 一个人走完全程；
  • 两人相向而行，相遇走完全程；
  • 两人各自负责走完一边，最终相遇于中间一点。
• 对于第①种情况：
  • 选择一个人向更近的一端点走，然后折返走完全程：ans=min(ans,min((n+min(n-p1,p1))/v1,(n+min(n-p2,p2))/v2))。
• 对于第②种情况：
  • 计算每个人各自走到端点的较大时间：ans=min(ans,max((n-p1)/v1,p2/v2))。
• 对于第③种情况：
  • 两种选择，考虑二分答案，二分两人最终相遇的点的位置，计算所需的最短时间。
  • 此过程中，计算左边的人所走的时间：t1=(mid+min(mid-p1,p1))/v1，右边的人所走的时间：t2=(n-mid+min(n-p2,p2-mid))/v2。如果 $t1<t2$，那么说明可以向右端收缩，每次更新答案ans=min(ans,max(t1,t2))。
• 注意：
  • 题意精确到 $1\times 10^{-6}$ ，但实际应精确到 $1\times 10^{-7}$ 。（别问我为什么）
  • 若 $p_1<p_2$，则交换 $p_1,p_2$ 与 $v_1,v_2$，使得从左到右保证从小到大。

代码：

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-7,INF=1e9;
int T;
double n,p1,p2,v1,v2;
int main(){
    cin>>T;
    while(T--){
    	cin>>n>>p1>>v1>>p2>>v2;
    	if(p1>p2){//交换
    		swap(p1,p2);
    		swap(v1,v2);
    	}
    	double ans=INF;
		ans=min(ans,min((n+min(n-p1,p1))/v1,(n+min(n-p2,p2))/v2));//第①种情况
		ans=min(ans,max((n-p1)/v1,p2/v2));//第②种情况
		double l=p1,r=p2;
		while(r-l>eps){
			double mid=(l+r)/2;
			double t1=(mid+min(mid-p1,p1))/v1;//左边
			double t2=(n-mid+min(n-p2,p2-mid))/v2;//右边
            ans=min(ans,max(t1,t2));//更新答案
			if(t1<t2)
				l=mid;
			else
				r=mid;
		}
		printf("%.10f\n",ans);
	}
    
    return 0;
}

后记：如有错误或不足请 dalao 指出。（点个再走呀！）