题解：CF2157E Adjusting Drones

· · 题解

Solution

首先考虑若操作次数 \ge ans，则一定也满足条件，所以，二分。

考虑对于一个 x 如何 check。

考虑对于数的相对顺序是没有用的，直接统计个数即可。那么按值域从大到小考虑，相当于将 a_i 向后走 x 步，每遇到一个 0 就将这个 0 变为 1，然后 a_i 减 1。直到最后走完 x 步，再将最终这个位置加上 a_i。最后判断是否对于所有位置都满足 \le k 即可。

用并查集维护下一个 0 的位置。这样一个 check 的时间复杂度就是 O(n\alpha(n))。

总时间复杂度 O(n\alpha(n)\log_2 n)。

:::success[AC Code]

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(Tx, Ty) make_pair(Tx, Ty)
#define For(Ti, Ta, Tb) for(auto Ti = (Ta); Ti <= (Tb); Ti++)
#define Dec(Ti, Ta, Tb) for(auto Ti = (Ta); Ti >= (Tb); Ti--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
const int N = 2e5 + 5;
int n, k, a[N];
int fa[N * 6];
int cnt[N * 6];
int find(int x) {
    if (fa[x] == x) return x;
    fa[x] = find(fa[x]);
    return fa[x];
}
void U(int x, int y) {
    fa[find(x)] = find(y);
}
bool check(int x) {
    For(i, 1, n * 6 + 1) fa[i] = i;
    For(i, 1, n * 6 + 1) cnt[i] = 0;
    For(i, 1, n) cnt[a[i]]++;
    For(i, 1, n * 6 + 1) if (cnt[i]) U(i, i + 1);
    Dec(i, n * 2, 1) {
        if (cnt[i] <= 1) continue;
        int X = cnt[i] - 1, now = find(i);
        while (X && now <= i + x) {
            cnt[now] = 1;
            X--;
            U(now, now + 1);
            now = find(now);
        }
        cnt[i] = 1;
        if (X) {
            if (cnt[i + x] == 0) U(i + x, i + x + 1);
            cnt[i + x] += X;
        }
    } 
    For(i, 1, n * 6) if (cnt[i] > k) return 0;
    return 1;
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    cin >> T;
    while (T--) {
        cin >> n >> k;
        For(i, 1, n) cin >> a[i];
        int l = 0, r = 3 * n, ans = -1;
        while (l <= r) {
            int mid = l + r >> 1;
            if (check(mid)) {
                ans = mid;
                r = mid - 1;
            } else l = mid + 1;
        }
        cout << ans << '\n';
    }
    return 0; 
}

:::