E1. Submedians (Easy Version) - 题解
比赛与标签
比赛: Codeforces Round 1039 (Div. 2) 标签: binary search, data structures, dp, greedy, math 难度: *2200
喵喵，这道题是什么意思呀？
主人你好呀~！这道题是说，我们有一个长度为 n 的数组 a 和一个整数 k。
首先，我们要明白什么是“中位数”（median）喵~ 对于一个长度为 m 的数组，如果一个数 v 大于等于其中至少 ⌈m/2⌉ 个元素，并且小于等于其中至少 ⌈m/2⌉ 个元素，那么 v 就是这个数组的中位数啦。
然后，题目定义了一个“子中位数”（submedian）。如果一个数 v，在数组 a 中存在一个长度至少为 k 的子数组，并且 v 是这个子数组的中位数，那么 v 就是一个子中位数。
我们的任务就是，在所有可能的子中位数中，找到那个最大的 v_max，并给出任意一个让它成为中位数的、长度不小于 k 的子数组的左右端点 l 和 r，的说。
如何抓住最大的 "中位数" 呢？
这道题要求我们找到“最大”的子中位数，这种“最大/最小化某个值”的问题，通常都有一个很棒的 sifat（性质）——单调性！
我们可以想一想，如果一个比较大的数 v 可以成为子中位数，那么一个比它小的数 v' 是不是更容易成为子中位数呢？答案是肯定的喵！因为把判断标准 v 降低，原来大于等于 v 的数就仍然大于等于 v'，甚至可能有些原来小于 v 的数现在也大于等于 v' 了，这样满足中位数条件的可能性就更大了。
反过来，如果一个数 v 不能成为任何满足条件的子数组的中位数，那么一个比它更大的数 v' 就更不可能了，对吧？
这种单onotonicity（单调性）最适合用什么方法解决呢？当然是二分答案啦！我们可以在 [1, n] 的范围内二分我们想要检查的子中位数 v。
Check函数的设计
二分答案的核心在于 check(v) 函数，它需要回答：“v 是否可以是一个子中位数？”
为了判断 v 是否是某个子数组 b 的中位数，我们只需要关心 b 中有多少数是 >= v 的。根据定义，这个数量需要至少是 ⌈|b|/2 rceil。
这里有一个超级好用的技巧哦！我们可以把原数组 a 转化一下：
- 如果
a[i] >= v，我们就把它看作+1。 - 如果
a[i] < v，我们就把它看作-1。
这样一来，对于一个子数组，如果其中 +1 的数量（cnt_good）减去 -1 的数量（cnt_bad）大于 0，就说明 +1 的比 -1 的多。
我们来推导一下中位数的条件： cnt_good >= ⌈(cnt_good + cnt_bad) / 2⌉
- 如果子数组长度
len = cnt_good + cnt_bad是奇数，len = 2p+1，那么⌈len/2⌉ = p+1。条件是cnt_good >= p+1。因为cnt_bad = 2p+1 - cnt_good，所以cnt_bad <= p。此时，这个子数组经过+1/-1变换后的和cnt_good - cnt_bad >= (p+1) - p = 1。 - 如果子数组长度
len是偶数，len = 2p，那么⌈len/2⌉ = p。条件是cnt_good >= p。因为cnt_bad = 2p - cnt_good，所以cnt_bad <= p。此时，和cnt_good - cnt_bad >= p - p = 0。
总结一下，我们的 check(v) 函数就是要找一个长度 len >= k 的子数组 a[l...r]，使得它在 +1/-1 变换后：
- 如果
len是奇数，其和>= 1。 - 如果
len是偶数，其和>= 0。
优化查找过程
要高效地计算子数组的和，当然要用前缀和啦！我们先预处理出 +1/-1 数组的前缀和 prefix。
然后我们遍历所有可能的右端点 r（从 1 到 n），对于每个 r，我们需要找到一个左端点 l（l <= r-k+1），使得 prefix[r] - prefix[l-1] 满足上面的条件。
这个条件和子数组长度的奇偶性有关，而长度 r - l + 1 的奇偶性又和 r 与 l-1 的奇偶性有关。这就有点麻烦了喵...
别急，我们可以分类讨论！ 当我们固定 r 时，为了让 prefix[r] - prefix[l-1] 尽可能大，我们应该让 prefix[l-1] 尽可能小。
所以，在遍历 r 的同时，我们可以维护两个值：
min0: 在0到r-k范围内，所有偶数下标i对应的prefix[i]的最小值。min1: 在0到r-k范围内，所有奇数下标i对应的prefix[i]的最小值。
这样，对于每个 r：
- 如果
r是偶数：- 我们需要找一个偶数下标的
l-1，使得长度为偶数。条件是prefix[r] - prefix[l-1] >= 0，即prefix[r] >= min0。 - 或者找一个奇数下标的
l-1，使得长度为奇数。条件是prefix[r] - prefix[l-1] >= 1，即prefix[r] >= min1 + 1。
- 我们需要找一个偶数下标的
- 如果
r是奇数：- 我们需要找一个奇数下标的
l-1，使得长度为偶数。条件是prefix[r] - prefix[l-1] >= 0，即prefix[r] >= min1。 - 或者找一个偶数下标的
l-1，使得长度为奇数。条件是prefix[r] - prefix[l-1] >= 1，即prefix[r] >= min0 + 1。
- 我们需要找一个奇数下标的
只要其中任何一个条件满足，check(v) 就返回 true，表示 v 是一个合格的子中位数。如果遍历完所有的 r 都不满足，就返回 false。
通过二分搜索，我们就能找到最大的那个 v，同时在 check(v) 函数返回 true 的时候记录下对应的 l 和 r，问题就解决啦！
代码实现喵~
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
const long long INF = 1e18;
// check函数，判断v是否可以成为一个子中位数
// 如果可以，返回 {true, {l, r}}
// 如果不可以，返回 {false, {-1, -1}}
pair<bool, pair<int, int>> check(int v, const vector<int>& a, int k, int n) {
// b[i] = 1 if a[i] >= v, else -1
// prefix[i+1] 存储 b[0...i] 的和
vector<long long> prefix(n + 1, 0);
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + (a[i] >= v ? 1 : -1);
}
// min0: 在 [0, r-k] 范围内偶数下标的最小前缀和
// min1: 在 [0, r-k] 范围内奇数下标的最小前缀和
long long min0 = INF;
long long min1 = INF;
// min0_index/min1_index 记录取得最小值时的下标
int min0_index = -1;
int min1_index = -1;
bool found = false;
int last_l = -1, last_r = -1;
// 遍历所有可能的右端点 r
for (int r = 1; r <= n; r++) {
// 当子数组长度可以满足 >= k 时，我们开始更新最小前缀和
if (r >= k) {
int d = r - k; // l-1 的最大可能下标
// 根据 d 的奇偶性更新 min0 或 min1
if (d % 2 == 0) {
if (prefix[d] < min0) {
min0 = prefix[d];
min0_index = d;
}
} else {
if (prefix[d] < min1) {
min1 = prefix[d];
min1_index = d;
}
}
}
// 我们只需要找到一个满足条件的子数组即可，所以l,r可以一直更新
if (r % 2 == 0) { // 如果 r 是偶数
// 找奇数 l-1 (len=r-(l-1)为奇), 条件: prefix[r] - prefix[l-1] >= 1
if (prefix[r] >= min1 + 1) {
found = true;
last_l = min1_index + 1;
last_r = r;
}
// 找偶数 l-1 (len=r-(l-1)为偶), 条件: prefix[r] - prefix[l-1] >= 0
else if (prefix[r] >= min0) {
found = true;
last_l = min0_index + 1;
last_r = r;
}
} else { // 如果 r 是奇数
// 找偶数 l-1 (len=r-(l-1)为奇), 条件: prefix[r] - prefix[l-1] >= 1
if (prefix[r] >= min0 + 1) {
found = true;
last_l = min0_index + 1;
last_r = r;
}
// 找奇数 l-1 (len=r-(l-1)为偶), 条件: prefix[r] - prefix[l-1] >= 0
else if (prefix[r] >= min1) {
found = true;
last_l = min1_index + 1;
last_r = r;
}
}
}
if (found) {
return {true, {last_l, last_r}};
} else {
return {false, {-1, -1}};
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
// 二分答案 [1, n]
int low = 1, high = n;
int ans_v = 0;
int ans_l = -1, ans_r = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
auto result = check(mid, a, k, n);
if (result.first) { // 如果 mid 可以作为子中位数
ans_v = mid; // 更新答案
ans_l = result.second.first;
ans_r = result.second.second;
low = mid + 1; // 尝试更大的 v
} else { // 如果 mid 不行
high = mid - 1; // 只能尝试更小的 v
}
}
cout << ans_v << " " << ans_l << " " << ans_r << "\n";
}
return 0;
}时间与空间，都要精打细算！
时间复杂度: O(N log N) 的说。 二分答案的过程需要
log N次迭代。在每次迭代中，check函数需要O(N)的时间来计算前缀和并遍历一次数组。所以总的时间复杂度就是O(N log N)啦。空间复杂度: O(N) 的说。 我们主要需要一个
prefix数组来存储前缀和，它的长度是N+1，所以空间复杂度是O(N)。
猫娘的小总结
这道题真是一次有趣的冒险呢，喵~ 它把好几个知识点巧妙地融合在了一起：
- 二分答案: 看到“最大化最小值”或“最小化最大值”这类问题，一定要想想是否具有单调性，能不能用二分来解决哦！
- +1/-1 变换: 这是一个非常经典的技巧！当问题涉及到与某个阈值比较的元素个数时，可以尝试将问题转化为求和问题，这往往能大大简化问题。
- 前缀和与奇偶性: 前缀和是处理子数组问题的利器。这道题还额外考察了根据下标/长度的奇偶性进行分类讨论，这是对思维细致度的一个小考验。
希望这篇题解能帮到主人哦！多做这样的题目，你的算法思维一定会越来越敏捷的，加油喵~！