CF-1486D Max Median 题解

题目大意

给定长度为 n 的数组 a，找到一个子数组 a[l .. r]，满足长度至少为 k，中位数最大。 子数组 a[l..r] 是指数组连续的一部分，也就是 a[l], a[l+1], … a[r]，它的长度是 r - l + 1。

解题思路

一开始在想怎么二分。

枚举左端点，二分右端点。

二分中位数，二分长度。

发现都是不好求中位数。

看了下题解，发现他的思路真的好巧妙。

首先是二分中位数，但是他判断的不是中位数是不是x，而是是否存在中位数大于等于x的子数组。

然后是check函数，枚举每一个数，把小于x的数f[i]=-1，大于等于x的数f[i]=1。

如果一段区间的和大于等于1，说明这段区间的中位数大于等于x。

维护前缀和和区间最小前缀和。

定义sum为前缀和，minn[i]为1~i之间的最小前缀和。

枚举所有大于k的位置，如果sum[i]-minn[i-k]大于等于1，表示存在，否则不存在。

因为对于i为右端点长度为k的左端点为i-k+1，由前缀和定义可知，需要向前移动一位，才表示这段区间的区间和，而minn维护的最小前缀和，保证了以i为右端点的长度一定大于等于k，并且一定是以i为右端点的最大区间和。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define endl '\n'
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const int N = 2e5 + 5;
int a[N], f[N], sum[N], minn[N], n, k;

int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b);
}

ll qpow(ll a, ll b, ll mod) {
	ll ans = 1;
	while (b) {
		if (b & 1)	ans = (ans * a) % mod;
		a = (a * a) % mod, b >>= 1;
	}
	return ans % mod;
}

int check(int x) {
	rep(i, 1, n) {
		if (a[i] < x)	f[i] = -1;
		else f[i] = 1;
		sum[i] = sum[i - 1] + f[i];
		minn[i] = min(minn[i - 1], sum[i]);
		if (i >= k && sum[i] - minn[i - k] >= 1) return 1;
	}
	return 0;
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> k;
	rep(i, 1, n) cin >> a[i];
	int l = 1, r = n;
	int mid;
	while (l < r) {
		mid = l + r + 1 >> 1;
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	cout << l << endl;
	return 0;
}