P9822 [ICPC2020 Shanghai R] Walker 题解

wylnh · 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 指出。（点个再走呀！）