题解：P17143 [NOI 2026] 中位数（暂无数据）

· · 题解

为啥大家做法都这么复杂，吓哭了，这里提供一个不需要太多分类讨论的做法。

首先显然二分答案 mid，按照套路将 a_i\ge mid 的视为 1，其余视为 0。直观的想一想，将每个 1 单独分一段是很优的，因为在极端情况下，若 k 为偶数，我们最后会分成 k+1 段；若 k 为奇数，我们会分成 k+2 段。那么只需考虑如何消掉这多出来的 1\sim 2 段。

先考虑简单的 k 为偶数的情况。我们发现，想要消掉一段，那么就必须要存在两个相邻的中位数 \ge mid 的段，这样他们中间的空隙就消掉了；或者存在开头或结尾段的中位数 \ge mid，这样开头之前或结尾之后的段就消掉了。

考虑如何判断能否凑出相邻的中位数 \ge mid 的段（以下简称合法段）。假设说我们一开始有一对距离比较远的 1，他们起初自成一段，我们现在想要他们不断拓展最后成为相邻的合法段，那么拓展时就会让他们变成比较大的合法段，当段变大时是很难做的。但是仔细思考一下可以发现，我们没有必要去合并出大段，因为当一个合法段中的 1 的个数 \ge 2 时，必然存在相邻的两个 1 使得他们的距离 \le 3，这很好理解，因为如果每对相邻的 1 的距离都 >3，那么这不可能是一个合法段。

而对于两个距离 \le 3 的 1，我们很容易将他们凑成相邻的小合法段。例如 1001 可以凑成 10|01。这就说明我们凑大的合法段是完全没有必要的。

所以 k 为偶数的情况就迎刃而解了，判断是否存在距离 \le 3 的 1 或是距离开头或结尾 \le 2 的 1 即可。

接下来考虑 k 为奇数的段，也就是我们需要找到两个满足上述条件的段，我们可以预处理出每个后缀是否存在相邻合法段或结尾合法段，然后直接枚举靠前的相邻合法段或开头合法段即可，然后要注意一些细节。

其实可以一句话概括的，上面的细节都归结于：11 可以划分为 1|1，101 可以划分为 10|1，1001 可以划分为 10|01。

最后的话，其他题解也都提到了，注意特判 n\le 5 的情况，以及当 1 的个数低于 \lceil \frac{k+1}{2} \rceil 时是不可能合法的。

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

void init(int c, int t) {
    return;
}
int n, k, a[1000005], b[1000005], one[1000005];
int f[1000005][6][6], hou[1000005];
int now = 0;

int ch(int x) {
    for (int i = 1; i <= n; i++)
        b[i] = (a[i] >= x), hou[i] = 0;
    int m = 0;
    for (int i = 1; i <= n; i++)
        if (b[i])
            one[++m] = i;
    int xu = (k + 1) / 2;
    if (m < xu)
        return 0;
    if (k <= 5) {
        int d = k / 2, u = (k + 1) / 2;
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= d; j++)
                for (int k = 0; k <= u; k++)
                    f[i][j][k] = -1e9;
        f[1][0][0] = 1;
        if (!b[1])
            f[1][0][0] = -1;
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= d; j++) {
                for (int k = 0; k <= u; k++) {
                    int z = b[i];
                    if (!b[i])
                        z = -1;
                    f[i][j][k] = max(f[i][j][k], f[i - 1][j][k] + z);
                    if ((j - 1 >= 0 && f[i - 1][j - 1][k] + n >= 0) || (k - 1 >= 0 && f[i - 1][j][k - 1] >= 0))
                        f[i][j][k] = max(f[i][j][k], z);
                }
            }
        }
        return f[n][d - 1][u] + n >= 0 || f[n][d][u - 1] >= 0;
    }
    if (k % 2 == 0) {
        int f = 0;
        if (one[1] <= 2 || one[m] >= n - 1)
            f = 1;
        for (int i = 1; i < m; i++)
            if (one[i + 1] - one[i] <= 3)
                f = 1;
        return f;
    }
    for (int i = 1; i <= m; i++)
        if (one[i] <= 2 || one[i] >= n - 1 || (i + 1 <= m && one[i + 1] - one[i] <= 3))
            hou[i] = 1;
    for (int i = m - 1; i >= 1; i--)
        hou[i] = max(hou[i], hou[i + 1]);
    for (int i = 1; i <= m; i++) {
        if (one[i] <= 2 || (i - 1 >= 1 && one[i] - one[i - 1] <= 3))
            if (i + 1 <= m && (one[i + 1] - one[i] <= 2 || hou[i + 1]))
                return 1;
        if (one[i] <= 1 || (i - 1 >= 1 && one[i] - one[i - 1] <= 2))
            if (i + 1 <= m && (one[i + 1] - one[i] <= 3 || hou[i + 1]))
                return 1;
        if (i - 1 >= 1 && ((one[i] - one[i - 1] <= 2 && one[i] >= n - 1) || (one[i] - one[i - 1] == 3 && one[i] == n)))
            return 1;
    }
    return 0;
}

int median(int n_, int k_, std::vector<int> a_) {
    n = n_;
    k = k_;
    for (int i = 1; i <= n; i++)
        a[i] = a_[i - 1];
    int l = 1, r = n, ans = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (ch(mid))
            ans = mid, l = mid + 1;
        else
            r = mid - 1;
    }
    return ans;
}