[AGC057B] 2A + x

· · 题解

或许更好的阅读体验。

思路：

先将 a 从小到大排序，然后分析下性质，如果 a_n 操作过了，那么显然前面的 a_i 一定会操作至少一次，这是不劣的；所以要么 a_n 没操作，要么整个序列都操作了。

如果可以使得序列的极差 D <X，那么显然操作整体操作一次后一定可以将 D 变小，所以经过若干次操作后答案一定是 0。

否则一定不会操作最大值，因为是倍增形的，每次操作后极差 2mx - (2(mx - D) + X) = 2D - X \ge D，会比之前大。

于是只需要考虑不操作最大值的时候的解，即先将 a 从小到大排序，那么显然是要算出每个 a_i 操作到距离 a_n 最近的点，如果能变成 a_n，那就直接变；否则设到 a_n 左右分别是 l_i, r_i，那么问题转化为每个点选 l_i, r_i，使得极差最小了。

则将 l 从小到大排序，枚举最小值，那么显然当前 i 前面的 l_j(j < i) 都选的 r_j，于是容易算出极差。

考虑怎么求距离 a_n 最新的点，对于一个数 a_i，每次是一个区间扩展的过程：[a_i, a_i] \to [2a_i, 2a_i + X] \to [4a_i, 4a_i + 3X] \to \cdots，这是一个倍增的过程最多有 O(\log w) 个区间。

如果算出来这个极差 <X 就可以操作成 0，否则就是这个答案，时间复杂度为 O(n \log w)。

完整代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define lowbit(x) (x) & (-(x))
#define popcnt(x) __builtin_popcount(x)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e5 + 10;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
struct Node{
    ll l, r;
    inline bool operator<(const Node&rhs)const{
        return l < rhs.l;
    }
}A[N];
ll ans;
ll n, X, cnt;
ll a[N];
int main(){
    n = read(), X = read();
    for(int i = 1; i <= n; ++i)
      a[i] = read();
    sort(a + 1, a + n + 1);
    ans = a[n] - a[1];
    for(int i = 1; i < n; ++i){
        bool flag = 0;
        ll l = a[i], r = a[i];
        ll L = 0, R = 0;
        while(1){
            if(l <= a[n] && a[n] <= r){
                flag = 1;
                break;
            }
            if(l > a[n]){
                L = (r - X) >> 1;
                R = l;
                break;
            }
            l = (l << 1), r = (r << 1) + X;
        }
        if(flag)
          continue;
        A[++cnt] = {L, R};
        // cerr << L << ' ' << R << '\n';
    }
    sort(A + 1, A + cnt + 1);
    A[++cnt] = {a[n], a[n]};
    ll mx = a[n];
    for(int i = 1; i <= cnt; ++i){
        ans = min(ans, mx - A[i].l);
        mx = max(mx, A[i].r);
    }
    write(ans < X ? 0 : ans);
    return 0;
}