第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（上海）补题

发表于 更新于 分类于 ， 阅读次数：

2020 ICPC 上海赛区题解

按过题人数由多到少补题

D. Walker

题意

一段区间$[0,n]$，两个人一个从$p_1$出发以$v_1$的速度行走，另一个从$p_2$出发以$v_2$的速度行走，求两个人一起覆盖这段区间的最短时间。

思路

分4种情况

  1. 其中一个人走完全程
  2. 两个人对着走
  3. 两个人先向中间走，再折返
  4. 先向两边走再到中间

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
//#define int ll
#define debug(x) std:: cerr << #x << " = " << x << std::endl;
const int maxn=2e5+10,inf=0x3f3f3f3f,mod=1000000007;
const double eps=1e-7;
signed main(signed argc, char const *argv[])
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        double n,p1,v1,p2,v2;
        cin>>n>>p1>>v1>>p2>>v2;
        if(p1>p2)
        {
            swap(p1,p2);
            swap(v1,v2);
        }
        double l=0,r=min({(n+min(n-p1,p1))/v1,(n+min(n-p2,p2))/v2,max((n-p1)/v1,p2/v2)});//1走完全程,2走完全程,对穿
        double ans=r;
        while(r-l>eps)
        {
            double mid=(l+r)/2;
            auto f=[](double p,double v,double t){
                double d=v*t;//p点出发,t时间行走距离
                if(d<p)//并不能走完
                    return (double)0;
                return max(max(p,d-2*p+p),p+(d-p)/2);//先向两侧走,先向中间走最大覆盖区间
            };
            double s1=f(p1,v1,mid)+f(n-p2,v2,mid);
            double s2=f(n-p1,v1,mid)+f(p2,v2,mid);
            if(s1>=n||s2>=n)
                ans=min(ans,mid),r=mid;
            else
                l=mid;
        }
        cout<<setiosflags(ios::fixed)<<setprecision(9)<<ans<<endl;
    }
    return 0;
}

M.Sky Garden