题解 AT_arc129_b Range Point Distance

AT_arc129_b Range Point Distance

简要题意

给定 $N$ 对 $L_i, R_i$，然后在每次给出后都要选一个 $x$ 使得 $x$ 到之前给出的所有区间的距离 $dist$ 的最大值最小。一个 $x$ 到区间 $l,r$ 的距离定义为 $dist=\max(0, l - x, x - r)$。

策略分析

既然我们每次都要输出答案，那我们不妨从 $dist$ 的定义入手，我们发现在这个定义中，当其结果不为 $0$ 时只有两种情况，要么 $l$ 在 $x$ 右边，要么 $r$ 在 $x$ 左边。那么我们考虑现在有一堆区间，因为我们求的是 $x$ 到所有区间距离的最大值，所以其实我们需要关心的，能够对我们答案造成影响的值就是最靠右的 $L$ 和最靠左的 $R$。得到这个结论后剩下的就比较简单了，我们只需要每次输入一个区间都更新一下这个关键的 $L$ 和 $R$ 即可。

我们现在知道了能够对我们答案造成影响的两个关键点，那么答案如何求解呢，我们进行分类讨论。

• 当 $L \le R$ 时，意味着之前输入的所有区间都有一个共同的交集 $[L,R]$，这个结论直接从 $L,R$ 的定义得出，那么我们随便在 $L,R$ 里怎么选都是 $0$，所以要找的最小值就是 $0$。
• 当 $L >R$ 时，以 $L$ 为左端点的区间和以 $R$ 为右端点的区间一定是之前输入的所有区间里距离最远的一组，只有这一对区间才会产生到 $x$ 的最大值。那么这个最大值最小当且仅当 $x$ 取在 $L,R$ 正中间，又因为要去最大值所以此时 $dist = \left \lceil \frac{L + R}{2} \right \rceil$。

分析出这两条以后直接在线做就好了，时间复杂度是线性的。

参考代码

#include <iostream>
#include <cstdio>
#define LL long long
using namespace std;

namespace SHAWN {
    const LL INF = 1e9 + 7;
    LL n, sl = -INF, sr = INF;
    signed work()
    {
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            LL l, r; cin >> l >> r;
            sl = max(sl, l), sr = min(sr, r);
            // 更新两个关键点
            if (sr >= sl) { cout << "0\n"; }
            else cout << ((sl - sr + 1) >> 1) << '\n';
            // 按照刚刚的分类讨论进行输出
        }
        return 0;
    }
}

signed main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}