2020ICPC上海站 D题 Walker 分类讨论+二分

传送门：https://ac.nowcoder.com/acm/contest/9925/D

题意

在一段[0,n]的区间内，有两个人分别站在p1和p2的位置，都有各自的速度v1,v2。 问：如何用最少时间能覆盖[0,n]区间，也就是怎么走完全程？

思路

如果一直分类讨论的话，官方解答是有13种，不过就凭我们这个猪脑子怎么可能想出来，所以我们就按以下三种分别讨论。

  • 一个人走完全程 ans=min((min(n−p1,p1)+n)/v1,(min(n−p2,p2)+n)/v2)
  • 两个人对向走完全程 ans=min(ans,max((n−p1)/v1,p2/v2))
  • 两个人分别以一个间断点mid，p1走[0,mid]，p2走[mid,n]，走完全程 二分mid，然后取最小值。

Code（55MS）

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
47
48
49
50
51
52
53
54
55
##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

##define INF 0x3f3f3f3f
##define lowbit(x) x & (-x)
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)

// const ll mod = 998244353;
// const ll mod = 1e9 + 7;
// const double eps = 1e-6;
// const double PI = acos(-1);
// const double R = 0.57721566490153286060651209;

double Clac(double n, double p, double v) {
    return (min(n - p, p) + n) / v;
}

void solve() {
    int _;
    scanf("%d",&_);
    while(_--) {
        double n, p1, v1, p2, v2;
        scanf("%lf%lf%lf%lf%lf",&n,&p1,&v1,&p2,&v2);
        if(p1 > p2) {
            swap(p1, p2); swap(v1, v2);
        }
        double ans;
        // 一个人走完
        ans = min(Clac(n, p1, v1), Clac(n, p2, v2));
        // 两个人对向走完
        ans = min(ans, max((n - p1) / v1, p2 / v2));

        // 以mid为分界线，二分求最小
        double l = p1, r = p2;
        for(int i = 1;i <= 100; i++) {
            double mid = (l + r) / 2.0;
            double ans1 = Clac(mid, p1, v1);
            double ans2 = Clac(n - mid, p2 - mid, v2);
            ans = min(ans, max(ans1, ans2));
            if(ans1 <= ans2) l = mid;
            else r = mid;
        }
        printf("%.10lf\n",ans);
    }
}

signed main() {
    sovle();
}

如果当时没有死磕这道题，那就会有大量的时间做其他题了。 这是第三次死盯一道题，如果还有下次，不可能有下次了！！！

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/12/17/2020-icpc-shanghai-d/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！