CF2800C 题解

题目大意：选择一个区间 \([l,r]\)，将里边的数翻转并 \(\times 2\)，求 \(\max\limits_{i=1}^{n-1}|a_i-a_{i+1}|\) 的最小值。

这道题要求最大值最小，很容易可以想到二分。问题就转化成了：选择一个区间 \([l,r]\)，将里边的数翻转并 \(\times 2\)，能不能使得 \(\forall i\in [1,n-1],\ |a_i-a_{i+1}|\leqslant x\)。

因为我的代码中写的是 \((i-1,i)\) 的形式，所以下文改成 \((i-1,i)\) 的形式。

考虑 check。

我们发现存在 \(|a_{i-1}-a_i|>x\) 时，想要合法，\(|a_{i-1}-a_i|>x\) 就不能全在翻转区间里或翻转区间外，因为前者会导致差距变为 \(2\) 倍，后者无法消除不合法对。

我们发现当 \(|a_{i-1}-a_i|>x\) 的对数 \(\geqslant 3\)，是无法通过一次翻转加倍操作变得合法。因为总是有至少一对 \(|a_{i-1}-a_i|>x\) 全在翻转区间里或翻转区间外，无法消除。

如图，我们发现当 \(|a_{i-1}-a_i|>x\) 的对数 \(=2\)，设为 \((i-1,i)\) 和 \((u-1,u)\)，这样就只能翻转 \([i,u-1]\)。判断 \(|2\times a_i-a_u|\) 和 \(|2\times a_{u-1}-a_{i-1}|\) 是否 \(\leqslant x\) 以及翻转区间内原来合法的对是否翻倍后还是合法。

我们发现当 \(|a_{i-1}-a_i|>x\) 的对数 \(=1\)，设为 \((i-1,i)\)，翻转区间的一边肯定还是要在对内，另一边就可以任意一个点了。注意：翻转区间内原来合法的对翻倍后还要是合法。

当区间的另一边在右侧，如图，我们于是枚举 \(j\)，并检查是否合法。注意：翻转到 \(n\) 的情况也是不可忽略的。

同理，左侧也是枚举。注意：翻转到 \(1\) 的情况也是不可忽略的。

注意一下细节和边界就好了。

Code

#include 
using namespace std;
const int N = 3e5 + 5;
int a[N], n;
int check(int x) {
    if(n == 2) {
        if(abs(a[1] * 2 - a[2]) <= x || abs(a[1] - a[2] * 2) <= x || abs(a[1] - a[2]) <= x) return true;
        else return false;
    }
    for(int i = 2; i <= n; i++) if(abs(a[i] - a[i - 1]) > x) {
        int u = 0;
        for(int j = i + 1; j <= n; j++)
            if(!u && abs(a[j] - a[j - 1]) > x) u = j;
            else if(abs(a[j] - a[j - 1]) > x) return false;
        if(u) {
            if(abs(2 * a[u - 1] - a[i - 1]) <= x && abs(a[u] - 2 * a[i]) <= x) {
                for(int j = i + 1; j <= u - 1; j++) if(2 * abs(a[j - 1] - a[j]) > x) return false;
                return true;
            } else return false;
        } else {
            for(int j = i + 1; j <= n; j++) {
                if(abs(2 * a[j - 1] - a[i - 1]) <= x && abs(a[j] - 2 * a[i]) <= x) return true;
                if(2 * abs(a[j - 1] - a[j]) > x) break;
                if(j == n && abs(2 * a[n] - a[i - 1]) <= x) return true;
            }
            if(i == n && abs(2 * a[n] - a[n - 1]) <= x) return true;
            for(int j = i - 1; j >= 2; j--) {
                if(abs(2 * a[i - 1] - a[j - 1]) <= x && abs(2 * a[j] - a[i]) <= x) return true;
                if(2 * abs(a[j - 1] - a[j]) > x) break;
                if(j == 2 && abs(2 * a[1] - a[i]) <= x) return true;
            }
            if(i == 2 && abs(2 * a[1] - a[2]) <= x) return true;
            return false;
        }
    }
    return true;
}
void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int L = 0, R = 1e6 + 5, ans;
    while(L <= R) {
        int mid = L + R >> 1;
        if(check(mid)) R = mid - 1, ans = mid;
        else L = mid + 1;
    }
    cout << ans << "\n";
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int T; cin >> T;
    while(T--) solve();
    return 0;
}