题解：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)

。

AC Code

CPP

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

题解：CF2157E Adjusting Drones

文章操作

Solution

相关推荐

评论

题解：CF2157E Adjusting Drones