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

_Ch1F4N_ · 2026-07-24 23:10:00 · 题解

场上过了写个题解。

说实话这个题有点难的。

二分 mid，将 <mid 看成 -1 而 \geq mid 看成 1，目标是将原序列划分为 k 段满足段内和 \geq 0 的至少有 \left\lceil\frac{k}{2}\right\rceil 段。

一个重要观察是这个限制其实很容易满足，具体而言我们直接找到 \left\lceil\frac{k}{2}\right\rceil 个 1（如果找不到肯定没法满足了），如果这些 1 之间的间隙消失或者与开头结尾的间隙消失的足够多就可以了。更具体地，根据 k 的奇偶性需要要求一个或者两个间隙消失。

所以为了使得间隙消失我们可能会取一些 \geq 0 的段而不是单独的 1。并且注意，限制还没完，我们需要没被选入段中的数可以被拆成足够多的段来满足一共 k 段的限制。

引出另一个重要观察，如果直接存在一些相邻的 1 我们肯定赢了，而如果相邻的 1 不存在那么我们取的 \geq 0 的段一定是满足 1,-1 交替的（或者可以拆分为两个 1,-1 交替的 \geq 0 的段），那么显然我们应该只需要取长度为 2 的 1,-1 就好了。不过这个是毛估估的分析，接下来严谨说明。

如果存在一个取的段 [l,r] 长度 >2，假设其中存在相邻的 1，记两个 1 位置为 i,i+1，首先容易发现 [l,i],[i+1,r] 至少有一个区间 \geq 0。假设 [l,r] 两侧都有相邻的其他段，那么我们取那个 \geq 0 的区间和另一个 1 即可达到和原来一样的间隙消失的效果并且把区间长度减 1 了，否则我们可以直接取这两个 1，同样达到和原来一样的间隙消失的效果并且把区间长度减 1 了。

如果不存在相邻的 1，那么一定是 1,-1 交替的结构（或者可以拆分为两个 1,-1 交替的 \geq 0 的段，此时可以直接拆开），只保留段首或者段尾长度不超过 2 的部分也可以达到和原来一样的间隙消失的效果。

并且我们拆分段的过程也会使得没被选入段中的数可以被拆成足够多的段来满足一共 k 段的限制更容易被满足，看上去全对了？

我们发现还有一个限制就是选出来的 \geq 0 的段本身不能超过 \left\lceil\frac{k}{2}\right\rceil 个，而上面的调整会增加段数？

但是先不急，我们先不管这个，根据上面的调整，我们会选一些 1 和 1,-1，并且要求有至少两组或者一组相邻。在满足了至少两组或者一组相邻后再去选择剩下的 1 作为选出来的段必然不会再导致段数超限，所以唯一的不合法情况就是满足至少两组相邻的过程导致段数超限制。这里至多会用到四段，而当 k \leq 5 时可能只能用三段，所以特判 k \leq 5 后的情况上述调整都是合法的（做 k \leq 5 就随便暴力 dp 一下）。

考虑枚举至少两组或者一组相邻的位置，在两组相邻一前一后时用前缀和优化一下。同时为了方便处理和开头结尾合并导致间隙消失可以认为开头结尾处都有一个段。这个地方容易做到 O(n)。

综上我们可以 O(n) check 一次，于是可以做到 O(n \log n) 的复杂度。