题解：P17143

A_small_WA · 2026-07-25 09:35:50 · 题解

成为全云南唯一一个场上草过去这题的，也是靠这题极限翻盘拿到 Cu。必须写一篇纪念一下。感觉题解区的大佬们的思路都太难了是怎么回事，这题真的有紫吗。

我们发现求 k 个数的中位数本质上是求第 \left\lceil\frac{k}{2}\right\rceil 大值，因此只关注前 \left\lceil\frac{m}{2}\right\rceil 个数的取值即可，不用考虑剩余的 \left\lfloor\frac{m}{2}\right\rfloor 个数的具体值。

将题目中划分为 k 段转化成 k-1 条分割线，正常情况下将 2 条分割线划在 a_i 的一左一右可以使这个区间的中位数为 a_i。

把 a 数组排序，设 a 数组降序排序后的数组为 c。考虑贪心，依次给 c_{n-1},c_{n-2},\dots,c_{\left\lceil\frac{m}{2}\right\rceil} 在原 a 数组中的位置的左右两边都加上分隔线，此时对于 k 为偶数则需 k 条分割线，k 为奇数则需要 k+1 条。

思考怎么减少分割线的使用，如果当你要划分 a_i 时，与 a_i 接近的位置已经有分割线，就可以省掉一条。具体的，我们发现如果分割出来的一个段中有两个元素，那么中位数仍然是他们中的最大值，因此你要分割 a_i 时，将 a_{i+1} 或 a_{i-1} 也分入这个区间是不影响结果的。

若 a_{i-3},a_{i-2},a_{i-1},a_{i+1},a_{i+2},a_{i+3} 中的一个已经在 a_i 之前被划分，那这次分割只需要一条分割线。具体如下图：（黑线表示原来已有的分割线，红线表示新加入的，三角表示之前已经被分割的元素，当前正在分割 a_i，每一行表示一种情况）

另一种情况是 i=0,1,n-2,n-1，这样你会发现在序列的最左边和最右边天然有一条分割线，因此这些情况也只需要一条分割线。

发现因此对于 k 为偶数，我们只需要从大往小找到第一个满足上述情况的 a_i，那么中位数就是 \min(a_i,a_{\left\lceil\frac{k}{2}\right\rceil})。

对于 k 为奇数，最简单的就是从大往小找到第二个满足上述情况的 a_i，但这里还有两种特殊情况要注意：

第一种是如果一个 a_j 的左右两边都分割线了，或者它一边有分割线，另一边是序列的首尾，那它就不需要分割线了。这样的 a_j 只要找出一个就满足条件，因此最后还要比较上面那段说的 a_i 和这种情况下的 a_j，中位数是 \min(\max(a_i,a_j),a_{\left\lceil\frac{k}{2}\right\rceil})。

第二种情况难以用文字描述，可以参考下图：

其中黑线和红线矛盾，因此对于 a_i 和 a_{i+3} 的分割需要特判，如果 a_{i+3} 已经和 a_{i+6} 分割过了，那 a_i 就依然只能用两条分割线，不能计入满足条件的 a_i。

写完上面的所有，你会发现只过了 16,17 两个点，发现它们有共同性质是 k>5，然后发现 k=2,3,5 时我们的代码会因为边界问题失效。

接下来是拼好码时间：

对于 k=2，可以枚举断点 i 用双顶堆解决，具体见 这道题。

对于 k=3,5，可以直接用 DP 的方法，但我赛时太菜了没写出来，所以用了贪心，分类讨论即可。

于是就写完了。时间复杂度 O(n)。可能有部分内容表述不清，还有问题的可以私信问我。

这是蒟蒻的第 24 篇题解，感谢观看。