CF875E Delivery Club 题解

题意：

Petya 和 Vasya 是两个快递员。他们每天需要去 $n$ 个地点送信，其中这 $n$ 个点在同一条直线上。

由于公司内部的规定，送包裹必须按照某种特定的顺序依次送达。初始时 Petya 在位置 $s_1$，Vasya 在位置 $s_2$，并且送包裹的顺序为 $x_1, x_2, \cdots, x_n$。

他们以如下形式送包裹：当前 $i$ 个包裹均送达后，他们中的一个去送第 $i+1$ 个包裹 (可以和送第 $i$ 个包裹的人是同一个人，也可以是不同的人)，另一个人则在原地等候。

由于他们需要互相交流，他们带了一对通讯设备。这对通讯设备在距离比较远时通讯功能较差。因此 Petya 和 Vasya 想找到一种合适的送包裹方案 (假如顺序是预先知道的)，使得他们之间的最大距离尽可能的小。帮助他们确定在不违反规定的情况下，最大距离的最小可能值。

输入格式：

第一行包含三个非负整数 $n, s_1, s_2,~(1 \leq n \leq 10^5, 0 \leq s_1, s_2 \leq 10^9)$，表示送信地点的个数与 Petya 和 Vasya 的初始位置。

第二行包含 $n$ 个非负整数 $x_1, x_2, \cdots, x_n,~(x_i \leq 10^9)$，表示送包裹的规定顺序。

保证 $s_1, s_2, x_1, x_2, \cdots, x_n$ 互不相同。

输出格式：

输出一行一个整数，表示最大距离的最小可能值。

考虑二分这个最长距离 $d$ ，然后判断能否成立。

仔细观察可以发现，

这两个快递员一定是一个在某个 $x_i$ ，另一个去送下一个包裹（不一定是 $x_{i+1}$ 哦）

在最长距离的约束下存在两个不同的可行域，分别对应这俩人能不能送下一个包裹

但是这个可行域由之前的决策决定，而我们不知道最优决策是什么。

考虑反推（可能叫逆向推理比较好）。

下文中记 $A,B$ 以区分两个人，但是这个 $A,B$ 是相对的两者。

注：其实就是「一个人」和「另一个人」，为了语言上便于区分加的记号

定义可行域 $R_i$ 表示 $A$ 送掉第 $i$ 个包裹的后，$B$ 应处于的位置。

可以发现在 $A$ 送第 $i$ 个包裹前，如果 $B$ 不在 $R_i$ 内，$A$ 无法移动。

显然在 $A$ 送掉第 $n$ 个包裹的时候， $B$ 的可行域为 $R_n = [x_n-d,x_n+d]$ 。

注：你是否好奇为什么不能是 $B$ 送掉最后一个包裹？

那说明你没有理解这个相对性。这里的 $A$ 就是两者中的某个人， $B$ 就是不同于他的那个人。

然后考虑 $x_{n-1}$ 。

如果 $x_{n-1} \in R_n$ ，也就是第 $n-1$ 个包裹在 $B$ 的可行域

那么我们直接让 $B$ 来送掉第 $n-1$ 个包裹就好了，然后让 $A$ 送掉第 $n$ 个包裹。

因为当 $B$ 送掉第 $n-1$ 个包裹后，它在第 $n$ 个包裹的可行域，于是 $A$ 可以送第 $n$ 个包裹

故此时 $A$ 的可行域为 $R_{n-1} = [x_{n-1}-d,x_{n-1}+d]$ 。

因为它要保证 $B$ 能送掉第 $n-1$ 个包裹。
如果 $x_{n-1} \not\in R_{n}$ ，也就是第 $n-1$ 个包裹不在 $B$ 的可行域

这说明 $x_{n-1}$ 肯定不能由 $B$ 来送，只能由 $A$ 来送。

不然 $B$ 送了第 $n-1$ 个包裹后，$A$ 无法送第 $n$ 个包裹（别忘了假设哦）

于是此时的情况就是 $A$ 送掉第 $n-1$ 个和第 $n$ 个包裹。

故 $B$ 的可行域为 $R_{n-1} = R_n \cap [x_{n-1}-d,x_{n-1}+d]$ 。

因为它要保证在 $A$ 能送掉第 $n-1$ 个包裹（对应后面那个），并且要让 $A$ 能送掉第 $n$ 个包裹（对应前面的 $R_n$ ）。

不难发现这样的推理对于任意的 $i \le n$ 都成立

于是我们通过归纳法得到了 $A$ 送完第 $1$ 个包裹后 $B$ 的可行域 $R_1$ 。

注：依旧不要忘了相对性。这里的 $A$ 就是指某个人。

因为这个确实很绕，我自己写的时候都有点绕。

如果 $B$ 都不在 $R_1$ 中，那么 $A$ 是送不了第 $1$ 个包裹滴，那么一定无解。
如果 $B$ 在 $R_1$ 中，因为 $B$ 在送第 $1$ 个包裹前后没有动

所以还要保证 $A$ 与 $B$ 在初始状态下距离不超过 $d$ ，即 $|s_1-s_2| \le d$

然后对于过程中出现的空集（交集为空），一定无解。

否则一定存在某种方法使得这两个人可以送掉这些快递。

至此，我们做完了这题。

时间复杂度 $O(n \log \max_{x_i})$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(1e5+15))

int n,l,r,s1,s2,a[N];
void up(int &x,int y) { x < y ? x = y : 0;}
void down(int &x,int y) { x > y ? x = y : 0;}
bool work(int x)
{
    int l=a[n]-x, r=a[n]+x;
    for(int i=n-1; i>=1 && l<=r; i--)
        if(l <= a[i] && a[i] <= r) l=a[i]-x, r=a[i]+x;
        else up(l, a[i]-x), down(r, a[i]+x);
    return (l <= s1 && s1 <= r) || (l <= s2 && s2 <= r);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> s1 >> s2; 
    int l=min(s1,s2), r=max(s1,s2);
    for(int i=1; i<=n; i++) cin >> a[i], up(r,a[i]), down(l,a[i]);
    for(r-=l, l=abs(s1-s2); l<r; )
    {
        int mid = (l+r) >> 1;
        work(mid) ? r=mid : l=mid+1;
    }
    cout << l << '\n';
    return 0;
}