D. Max Median - 题解
比赛与标签
比赛: Codeforces Round 703 (Div. 2) 标签: binary search, data structures, dp 难度: *2100
题目大意喵~
你好呀，未来的算法大师！这道题是这样的喵：
我们拿到一个长度为 n 的数组 a，还有一个整数 k。我们的任务呢，是在这个数组里找到一个长度至少为 k 的连续子数组，并且这个子数组的中位数要尽可能大！最后，我们只要输出这个最大的中位数就可以啦。
这里对中位数的定义是：把一个数组排好序后，排在第 ⌊(数组长度 + 1) / 2⌋ 位置的那个数。比如说，[1, 2, 3, 4] 的中位数是 2，[3, 2, 1] 排序后是 [1, 2, 3]，中位数也是 2 呢。
解题思路大揭秘！
看到“最大化”一个值（这里是中位数），我们的猫猫直觉就要警觉起来啦！这种“最大化最小值”或者“最小化最大值”的问题，通常都可以用一个非常强大的武器——二分答案来解决，的说！
1. 答案的单调性与二分搜索
我们可以二分我们想要的答案，也就是那个最大的中位数 m。假设我们猜一个可能的中位数 x，然后去检查：是否存在一个长度至少为 k 的子数组，它的中位数大于等于 x 呢？
这个问题有一个非常棒的性质，叫做单调性：
- 如果存在一个子数组，它的中位数
>= x，那么对于任何一个比x小的数y(y < x)，这个子数组的中位数也一定>= y。 - 反过来，如果连一个中位数
>= x的子数组都找不到，那肯定也找不到中位数>= x+1的子数组啦。
有了这个单-调-性，我们就可以愉快地二分答案了！我们可以在 [1, n] 的范围内（因为数组里的数最大就是 n）二分查找这个最大的 x，使得 check(x) 函数返回 true。
2. 如何实现 check(x) 函数呢？
现在，所有的问题都集中到了如何高效地实现 check(x) 函数上。我们要判断的是：是否存在一个长度不小于 k 的子数组，其中位数 >= x。
直接处理中位数太麻烦了，我们来把它转化一下，喵~ 一个子数组的中位数 >= x 意味着什么呢？ 意味着，当我们把这个子数组排序后，它中间的那个数都比 x 大或者相等。这也就说明，在这个子数组里，大于等于 x 的数的数量，一定严格大于小于 x 的数的数量。 （举个例子：长度为 5 的数组，中位数是第 3 个数。要让它 >=x，至少要有 3 个数 >=x，那么 <x 的数最多只有 2 个。3 > 2。对于长度为 4 的数组，中位数是第 2 个数。要让它 >=x，至少要有 2 个数 >=x。但如果只有2个 >=x，另外2个 <x，排序后可能是 [<x, <x, >=x, >=x]，中位数是第二个 <x 的数，不满足。所以必须要有至少 3 个数 >=x，这样 <x 的数最多 1 个。3 > 1。所以这个性质是普适的！）
这个发现太重要啦！我们可以把原数组 a 变成一个只包含 1 和 -1 的辅助数组 b：
- 如果
a[i] >= x，那么b[i] = 1。 - 如果
a[i] < x，那么b[i] = -1。
现在，check(x) 的问题就变成了：在辅助数组 b 中，是否存在一个长度不小于 k 的子数组，其所有元素的和大于 0？
3. 前缀和与滑动窗口优化
要找子数组的和，前缀和是我们的好朋友！我们对辅助数组 b 计算前缀和，得到数组 p，其中 p[i] 表示 b 数组前 i 个元素的和。那么 b 中从 l 到 r 的子数组之和就是 p[r] - p[l-1]。
我们的目标是找到一对 l, r，满足：
r - l + 1 >= k（长度条件）p[r] - p[l-1] > 0（和大于0）
整理一下，就是对于每个 r，我们需要找到一个 l，使得 l <= r - k + 1 并且 p[r] > p[l-1]。 为了让 p[r] > p[l-1] 这个条件尽可能成立，我们应该让 p[l-1] 尽可能小。
所以，我们可以遍历所有可能的右端点 r（从 k 到 n）。对于每一个 r，我们需要在它左边所有合法的 l-1（也就是 0 到 r-k）中，找到一个最小的 p 值。 设 min_val = min(p[0], p[1], ..., p[r-k])。只要 p[r] > min_val，我们就找到了一个满足条件的子数组，check(x) 就可以返回 true 啦！
为了快速得到 min(p[0], ..., p[r-k])，我们可以再预处理一个数组，专门存放前缀和数组的“前缀最小值”。这样，整个 check(x) 函数的时间复杂度就从 O(n^2) 降到了 O(n)，非常高效！
总的来说，我们的算法就是：
- 二分答案
x。 - 在
check(x)函数中，将原数组转化为1/-1数组。 - 计算
1/-1数组的前缀和p。 - 计算
p数组的前缀最小值min_prefix。 - 遍历
r从k到n，检查是否有p[r] > min_prefix[r-k]。 - 根据
check(x)的结果，调整二分范围，直到找到最终答案。
代码实现喵~
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// check(x) 函数判断是否存在一个长度至少为 k 的子数组，其中位数 >= x
bool check(vector<int>& a, int k, int x) {
int n = a.size();
// p 是我们构造的辅助数组的前缀和数组
// 如果 a[i-1] >= x，贡献为 1；否则为 -1
vector<int> p(n + 1, 0);
for (int i = 1; i <= n; ++i) {
p[i] = p[i - 1] + (a[i - 1] >= x ? 1 : -1);
}
// min_prefix[i] 存储 p[0] 到 p[i] 的最小值
vector<int> min_prefix(n + 1);
min_prefix[0] = p[0];
for (int i = 1; i <= n; ++i) {
min_prefix[i] = min(min_prefix[i - 1], p[i]);
}
// 遍历所有可能的右端点 r，要求子数组长度至少为 k
for (int r = k; r <= n; ++r) {
// 我们要找一个左端点 l，使得 1 <= l <= r - k + 1
// 这对应到前缀和数组的下标是 l-1，范围是 0 <= l-1 <= r-k
// 我们需要 p[r] - p[l-1] > 0，即 p[r] > p[l-1]
// 为了让这个条件更容易满足，我们希望 p[l-1] 尽可能小
// 所以我们检查 p[r] 是否大于 p[0...r-k] 中的最小值
if (min_prefix[r - k] < p[r]) {
return true; // 找到了！
}
}
return false; // 没找到符合条件的子数组
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
// 二分搜索答案的范围是 [1, n]，因为数组元素值在 1 到 n 之间
int low = 1, high = n, ans = 1;
while (low <= high) {
int mid = low + (high - low) / 2; // 用这种方式防止溢出，是个好习惯喵~
if (check(a, k, mid)) {
// 如果中位数可以达到 mid，说明 mid 可能就是答案，或者答案更大
ans = mid;
low = mid + 1;
} else {
// 如果中位数达不到 mid，说明答案肯定比 mid 小
high = mid - 1;
}
}
cout << ans << endl;
return 0;
}复杂度分析的说
时间复杂度: O(n log n) 的说。 二分答案的过程需要
log n次迭代。在每次迭代中，check函数需要O(n)的时间来构建前缀和数组和前缀最小值数组，并进行一次遍历。所以总的时间复杂度就是O(n log n)。对于n = 2*10^5的数据规模，这个速度是完全可以接受的！空间复杂度: O(n) 的说。 我们在
check函数中需要两个额外的数组p和min_prefix，它们的长度都和n成正比，所以空间复杂度是O(n)。
知识点与总结
这真是一道非常漂亮的题目，融合了好几种算法思想呢，喵~
二分答案 (Binary Search on Answer)：这道题是二分答案思想的经典应用。当你要求解一个具有单调性的“最大化/最小化”问题时，一定要先想想二分！
问题转化 (Problem Transformation)：解题的精髓在于将复杂的“中位数”条件，通过
+1/-1赋值法，巧妙地转化为了一个更简单的“子数组和大于0”的问题。这种转化思维在算法竞赛中非常重要，能化繁为简。前缀和优化 (Prefix Sum Optimization)：前缀和是处理连续子数组问题的利器。它能将求任意子数组和的时间从
O(length)降到O(1)，是优化算法的关键一步。
希望这篇题解能帮助你理解这道题的思路！继续加油，你一定能成为更厉害的算法大师的，喵~！