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

· · 题解

提供一种完全不用数据结构且不用过多分讨的 O(n\log n) 做法，会提供思考过程。

首先根据数据范围不能直接 DP，很难不想到二分答案转成 \text{01} 判可行（中位数为 1），则我们需要不少于一半的段中位数为 1，考查后面的性质。一种 naive 的 idea 是，把 1 全部尽量单独提取为连续段。很难不注意到这么做中位数为 1 的段数不少于中位数为 0 的段数 -1。首先排除 1 个数少于 k 的一半，当超过时我们可以任意将多余的 1 废弃与 0 放一起。接下来可以对 k 奇偶性简单分讨。

$k$ 为奇数时这样的贴贴需要至少 $2$ 次。这样分讨也太麻烦了，不妨搞个 DP。当至少 $2$ 个 $1$ 出现在序列头或尾一定可行，不少于 $3$ 个 $1$ 在一起时，除 $k=3$ 均可行。于是我们只需考虑 $11$，$1100$ 状和 $10$ 状中位数为 $1$ 段结构（$1,0$ 换位等同），而更长的结构一定能由以上拼接故不考虑，奇数长度仍能拓展故不考虑。对之进行线性 DP，记 $f_{i,j,k,0/1}$ 表示到 $i$ 位置，贴贴对数为 $j$（$\le 2$），浪费独立 $1$（每出现 $1100$ 结构记一次）个数（$\le 4$），是否存在中位数为 $1$ 段真的以该位结尾，值记录最少征用中位数为 $1$ 段数，不存在设为无穷大。转移能常数时间枚举上述 $01$ 数量关系结构做到，最终统计是否浪费后有效 $1$ 不小于 $k$ 一半且贴贴对数为 $2$，征用段数不超过 $k$ 一半（上取整）的即可。