ICPC 2020上海 D. Walker(精度二分+分类讨论)

2023/11/30 4:53:30

题意：
给定一段长度为n的区间，给定两个人的初始位置和速率，规定这两个人可以在任意时刻朝向任意方向走，转向不耗费时间。

求：所有区间都被至少一个人走过一遍所需的最少时间。

思路：

按照贪心思路，我们将所有情况大体概括为三大类

分类讨论
1.一个人走完全程
2.两个人碰头之后继续走
3两个人碰头之后就停止了

对于第一个情况没什么好说的，就用一个人的速度和他需要走的路程算就好了。

对于第二个情况，既然碰头之后还要走，我们尽量满足他重复走的区间最小，那么就是两个人相向的去走

二分
对于第三个情况，我们有两种子情况。

1.两人现实背箱走，走到端点之后掉头到了相向走的局面，最终在一个mid点回合

2.两个人先是相向走，走到mid点之后碰头，然后同时调转方向，两人再背向朝着端点走去，两人都走到端点之后结束。

所以我们就要二分这个mid点到底在哪里。

我们如何去评判这个二分的标准呢？也就是我们的check函数要怎么去写呢？
假设a的初始位置永远是小于等于b的，我们设碰头的点是mid
那么在第三种情况下a的最短路程就是mid+min(a.pos,mid-a.pos)，最短时间用路程除以速率即可。

我们发现如果两个人走的时间尽可能一致那么两个人都在各自的速率下走了尽可能多的路程。所以我们要求两个人在最小情况下走的时间差距要尽可能的小。

#include<bits/stdc++.h>
using namespace std;
const long double eps = 1e-7;
long double x;
struct Node
{
    long double x,v;
}a,b;
bool check(long double mid)
{
    return (mid+min(a.x,mid-a.x))/a.v>((x-mid)+min(x-b.x,b.x-mid))/b.v;
}
long double solve()
{
    long double l=a.x,r=b.x;//两人位置
    while(r-l>eps)
    {
        long double mid=(l+r)/2;
        if(check(mid))
           r=mid;
        else
           l=mid;
    }
    return max(l/a.v+(min(a.x,l-a.x))/a.v,((x-l)+min(x-b.x,b.x-l))/b.v);//要两个人都走到端点或者mid点才可以，短板效应要求取用时长的人
}
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;
    for(cin>>t;t;t--)
    {
        cin>>x>>a.x>>a.v>>b.x>>b.v;
        if(a.x>b.x)
            swap(a,b);
        long double ans=(x+min(a.x,x-a.x))/a.v;//第一种情况
        ans=min(ans,(x+min(b.x,x-b.x))/b.v);//第一种情况
        ans=min(ans,max(b.x/b.v,(x-a.x)/a.v));//第二种情况
        ans=min(ans,solve());
        cout<<fixed<<setprecision(10)<<ans<<'\n';
    }
    return 0;
}