题解 | #中位数#

题目大意

给定长度为 $n$ 的整数数组 $a$ 和整数 $m$ ，考虑所有长度 $\ge m$ 的连续子数组，对每个子数组取其下中位数（偶数长度取两中间较小者），求这些中位数中的最大值。

下中位数定义：长度为 $L$ 的序列排序后取第 $\lceil L/2 \rceil$ 个元素（1-indexed）
例如：[2,7,3,5] → 排序 [2,3,5,7] → 中位数 = 第 2 个 = 3

解题思路

核心观察

答案一定是原数组中的某个元素（因为中位数来自子数组元素）
直接枚举所有子数组不可行（ $O(n^2)$ 子数组，每组排序 $O(n\log n)$ → 超时）

二分答案 + 判定转化

我们二分答案 $x$ ，问题转化为：

是否存在一个长度 $\ge m$ 的子数组，其中位数 $\ge x$ ？

如何高效判定？

构造辅助数组 $b$ ：

b[i] = \begin{cases} +1 & \text{如果 } a[i] \ge x \\ -1 & \text{其他情况} \end{cases}

关键性质：
子数组的中位数 $\ge x$ 当且仅当 其对应的 $b$ 子数组和 $\ge 1$ 。

证明：设子数组长度 $L$ ， $\ge x$ 的元素有 $cnt$ 个
中位数 $\ge x$ ⇨ $cnt \ge \lceil L/2 \rceil$ ⇨ $2cnt > L$ ⇨ $\sum b = 2cnt - L \ge 1$

前缀和优化判定

用前缀和 delta[i] = b[0]+...+b[i-1]，则子数组 v[l..r] 的和为 delta[r+1] - delta[l]。

要判断是否存在长度 $\ge m$ 的子数组满足和 $\ge 1$ ，只需：

遍历右端点 $i$ （对应前缀和 delta[i]）
维护 min_prefix = min(delta[0], ..., delta[i-m])
若 delta[i] - min_prefix >= 1，则存在合法子数组

时间复杂度： $O(n)$ 每次判定

算法步骤

去重排序：将数组元素去重并排序（用于二分候选答案）
二分答案：在排序后的数组上二分索引
判定函数 check(x)：
- 构造前缀和数组 delta
- 维护最小前缀和 min_prefix
- 若存在 delta[i] - min_prefix > 0（即 $\ge 1$ ），返回 true
输出最大可行答案

复杂度分析

时间复杂度：
- 每组测试数据：
  - 使用 set 去重并构建 search 数组： $O(n \log n)$
  - 二分答案：最多 $O(\log n)$ 次迭代（因为去重后最多 $n$ 个不同值）
  - 每次 check 函数： $O(n)$
  - 小计： $O(n \log n)$
- 题目保证所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$
- 因此总时间复杂度为： $O\left( \sum (n_i \log n_i) \right) \leq O\left( (\sum n_i) \cdot \log (\max n_i) \right) = O(2 \times 10^5 \cdot \log 10^5) \approx O(3.6 \times 10^6)$ 完全可以通过。
空间复杂度： $O(n)$ ，用于存储数组、前缀和及去重后的候选值。

代码实现

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

bool check(int x, vector<int>& v, int m) {
    int n = v.size();
    vector<int> delta(n + 1, 0);
    // 构造前缀和：>=x 为 +1，否则 -1
    for (int i = 0; i < n; i++) {
        delta[i + 1] = delta[i] + (v[i] >= x ? 1 : -1);
    }
    
    int min_prefix = 0; // delta[0] = 0
    // 遍历右端点 i（对应子数组结束于 i-1）
    for (int i = 1; i <= n; i++) {
        if (i >= m) {
            // 检查是否存在左端点 j ∈ [0, i-m] 使得 delta[i]-delta[j] >= 1
            if (delta[i] - min_prefix > 0) {
                return true;
            }
            // 更新 min_prefix：加入 delta[i - m + 1]（为下一轮准备）
            min_prefix = min(min_prefix, delta[i - m + 1]);
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int q;
    cin >> q;
    while (q--) {
        int n, m;
        cin >> n >> m;
        vector<int> v(n);
        set<int> st;
        for (int i = 0; i < n; i++) {
            cin >> v[i];
            st.insert(v[i]);
        }
        // 去重并排序
        vector<int> search(st.begin(), st.end());
        int l = 0, r = (int)search.size() - 1;
        int ans = 0;
        
        // 二分答案（在排序后的数组上）
        while (l <= r) {
            int mid = (l + r) / 2;
            if (check(search[mid], v, m)) {
                ans = mid;      // 记录可行答案
                l = mid + 1;    // 尝试更大的值
            } else {
                r = mid - 1;    // 尝试更小的值
            }
        }
        cout << search[ans] << '\n';
    }
    return 0;
}