抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

CodeForces 875E Delivery Club

This is a picture without description

pufanyi

题解

发布于：Jan 12, 2019

有两个快递员，分别在 s1,s2(0≤s1,s2≤109)s_1, s_2(0\le s_1,s_2\le 10^9)，现在有n(1≤n≤100000)n(1\le n\le 100000) 个任务，每个任务 xix_i 表示要将货物送到 xix_i，让任何一个快递员到xix_i 都可以。由于快递员之间需要有对讲机联系，请你设计一种方案使得两个快递员之间的最长距离最短。

先输入 n,s1,s2n,s_1,s_2，在一行nn 个整数xix_i。

题解

CF 如此多的二分 + 贪心，但我就是想不出来……

首先二分答案。

难点是在如何判断答案合法。

显然正着做是不行的，所以我们考虑倒着做。

我们考虑现在二分的距离为 LL，枚举到第ii 步，如果两个快递员中至少有一个的起点出现在 [li,ri][l_i,r_i] 的范围内，且两个快递员相距不超过LL，那么是合法的。

现在考虑从 [li+1,ri+1][l_{i+1},r_{i+1}] 向[li,ri][l_{i},r_{i}]转移。

显然，两个快递员中只有一个快递员动，而不动的那个快递员必须已经在[xi−L,xi+L][x_i-L,x_i+L]。

我们考虑下面两种情况：

如果 xi∈[li,ri]x_i\in[l_i,r_i]，那么只要有一个快递员已经在[xi−L,xi+L][x_i-L,x_i+L] 里即可，我们让另一个快递员走到 xix_i，而因为xi∈[li,ri]x_i\in[l_i,r_i]，所以这位快递员在[li,ri][l_i,r_i] 里了，且两个快递员相距不超过LL。所以li=xi−L,ri=xi+Ll_i=x_i-L, r_i=x_i+L。

如果 xi∉[li,ri]x_i\notin [l_i,r_i]，考虑不动的快递员，首先必须在[xi−L,xi+L][x_i-L,x_i+L] 里，又由于 xi∉[li,ri]x_i\notin[l_i,r_i]，故他也必须在[li,ri][l_i,r_i] 里，而到 xix_i 的那个快递员没有什么特殊的要求了。所以li=max⁡(li+1,xi−L),ri=min⁡(ri+1,xi+L)l_i=\max(l_{i+1},x_i-L),r_i=\min(r_{i+1},x_i+L)。

代码

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
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 100005;
const int inf = 0x3f3f3f3f;

int n, s1, s2;
int aa[maxn];

inline bool check(int x)
{
    int l = -inf, r = inf;
    for(int i = n; i; --i)
    {
        if(l <= aa[i] && aa[i] <= r)
            l = aa[i] - x, r = aa[i] + x;
        else
            l = max(l, aa[i] - x), r = min(r, aa[i] + x);
    }
    return (l <= s1 && s1 <= r) || (l <= s2 && s2 <= r);
}

int main()
{
    scanf("%d%d%d", &n, &s1, &s2);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &aa[i]);
    int l = abs(s1 - s2), r = inf;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        if(check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    printf("%d\n", l);
    return 0;
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://pufanyi.github.io/oi-blog/CF875E/

更新于：Jul 2, 2023

CodeForces

贪心

二分

评论