P8978 「DTOI-4」中位数

给定一个长度为 $n$ 的整数序列 $a$，你可以进行以下操作不超过 $k$ 次： - 选择一个区间 $[l, r]$ 满足 $1 \leq l \leq r \leq n$，并将 $[l, r]$ 中的所有数替换为这个区间的中位数。 你要使得操作后 $a$ 的**最小值最大**。 关于此处中位数的定义：对于一个长度为 $len$ 的序列，其中位数定义为该序列中第 $\lceil \frac{len}{2} \rceil$ 小的数。

无

无

| $\textbf{Subtask}$ | $n$ | 分值 | | :------: | :------: | :------: | | $1$ | $1 \leq n \leq 10$ | $10 \operatorname{pts}$ | | $2$ | $1 \leq n \leq 100$ | $10 \operatorname{pts}$ | | $3$ | $1 \leq n \leq 10^3$ | $10 \operatorname{pts}$ | | $4$ | $1 \leq n \leq 10^4$ | $20 \operatorname{pts}$ | | $5$ | $1 \leq n \leq 10^5$ | $20 \operatorname{pts}$ | | $6$ | 无特殊限制 | $30 \operatorname{pts}$ | 对于 $100\%$ 的数据，$1 \leq n \leq 4 \times 10^5$，$0 \leq k \leq n$，$0 \leq a_i \leq 10^9$。