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;
}