题解：P11830 [省选联考 2025] 幸运数字（民间数据）

这都能蓝，我觉得是绿诶。

$\mathtt{Solution}$

原问题不是很好考虑，那么我们先进行转化：给定一个

x

，求

x

是否能成为中位数。

不难发现所有的区间

[l_{i,2},r_{i,2}]

就被分成了三类：严格在

x

左边的，包含

x

的，以及在

x

右侧的。

假设

x

左边最多有

M_1

个数，最少有

N_1

个数。

同理假设

x

右边/中间最多有

M_2,M_3

个数，最少有

N_2,N_3

个数。

接下来分类讨论：

$M_1<N_2$ ：即右边的数永远大于左边的数，此时我们发现包含 $x$ 的区间全部填成 $x$ 是最优的（自证不难）。那么 $x$ 是中位数只需要满足 $M_3+M_1-1>N_2$ 即可。
$M_2<N_1$ 与上种情况同理，不再阐述。
如果都不满足，那么此时只需要把包含 $x$ 的区间全部填成 $x$ 即可。因为可以把左右两边的数量调整成相等的，所以即 $x$ 可以成为中位数。

考虑了以上问题之后，你可以过

\mathtt{A}

性质，预计

60

分。

接下来思考如何把若干个

x

一起考虑。

先对

l_{i,2},r_{i,2}

离散化后，我们发现一段不包含

l_{i,2},r_{i,2}

的区间里面的

x

都是等价的。

后面排序离散化就行了，代码后面补。