CF1993D Med-imize

传送门

Solution

有一个显然的事实：被删除的块的大小一定是 $k$ 的整数倍。因此我们不妨将原先的操作变成：挑选 $\lfloor \dfrac{n-1}{m} \rfloor$ 个不重复的，大小为 $k$ 的区间进行消除。

由于中位数的确定，关注的是比它大 / 小的数的数量。又注意到所求为最大中位数，因此选用二分答案，将大于等于 $mid$ 的数改为 $1$，小于 $mid$ 的数改为 $-1$。设 $f_i$ 表示前 $i$ 个数中，消除了 $\lfloor \dfrac{i-1}{m} \rfloor$ 次，剩余的数之和的最大值。若 $f_n > 0$，则说明答案大于等于 $mid$。

对于第 $i$ 个数，可以不消除，也可以消除区间 $[i-k+1,i]$。状态转移方程见代码。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10;

int T, n, a[N], b[N], f[N], m;

bool check(int k)
{
	for (int i = 1; i <= n; i++) {
		b[i] = (a[i] >= k) ? 1 : -1;
		f[i] = 0;
		if (i <= m)
			f[i] = f[i - 1] + b[i];
		else if ((i - 1) / m == (i - 2) / m)
			f[i] = max(f[i - 1] + b[i], f[i - m]);
		else
			f[i] = max(b[i], f[i - m]);
	}
	return f[n] > 0;
}

void solve()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	int l = 1, r = 1e9, mid, ans = 1;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (check(mid)) {
			l = mid + 1;
			ans = mid;
		} else 
			r = mid - 1;
	}
	printf("%d\n", ans);
}

int main()
{
	scanf("%d", &T);
	while (T--) solve();
	return 0;
}