「NowCoder」中位数

题目大意：给出一个长度为 $n$ 的序列，问所有长度不小于 $len$ 的子区间的中位数最大是多少？$1 \leq len \leq n \leq 10^5$

由于一个区间的中位数是否大于等于 $x$ 只跟该区间内小于 $x$ 的数的个数和大于等于 $x$ 的数的个数有关，因此可以二分答案 $x$，把序列中所有小于 $x$ 的数标记为 $-1$，所有大于等于 $x$ 的数标记为 $1$。

贪心计算所有长度大于等于 $len$ 的区间的最大和，设 $sum[i]$ 表示区间 $[1,i]$ 的和，则以 $r$ 为右端点的长度大于等于 $len$ 的区间的最大和为

$$sum[r]-min\lbrace sum[l-1]\rbrace\ (l \in [1,r-len+1])$$

如果最大和大于 $0$，说明中位数大于等于 $x$，否则中位数小于 $x$。

#include <cstdio>
#include <algorithm>

const int N = 100005, maxn = 1e9;
int n, len, a[N];

int max(int x, int y) { return x > y ? x : y; }
int min(int x, int y) { return x < y ? x : y; }

bool check(int x) {
	int b[N] = {}, c[N] = {};
	for (int i = 1; i <= n; ++i) {
		b[i] = b[i-1] + (a[i] < x ? -1 : 1); //注意等于x的数也应标记为1
		c[i] = min(c[i-1], b[i]);
	}
//	int res = b[len];
//	for (int i = len + 1; i <= n; ++i) 
//		res = max(res, b[i] - c[i-len]);
//	return res > 0 ? true : false;
//	等价于以下代码
	for (int i = len; i <= n; ++i)
		if (b[i] > c[i-len]) return true; //注意这里是'>'而不是'>='
	return false;
}

int main() {
	scanf("%d%d", &n, &len);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	int l = 1, r = maxn;
	while (l < r) {
		int mid = l + (r - l + 1 >> 1);
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	printf("%d\n", l);
	return 0;
}

时间复杂度 $O(n \log n)$