CF1993D Med-imize

Alex_Wei · 2024-08-07 13:30:43 · 题解

CF1993D Med-imize

第一个被留下的位置之前删去的长度是 k 的倍数，所以第一个被留下的位置的下标模 k 余 1。类似可知第 i 个被留下的位置的下标模 k 和 i 同余。

已知总共会留下不超过 r = ((n - 1) \bmod k) + 1，二分答案 mid，则总共要留下至少 c 个不小于 mid 的数，满足 2c - 1 \geq \min(r, n)。设 f_i 表示保留 i 个数时 c 的最大值，对当前 a_j，设 t = ((j - 1) \bmod k) + 1，则 f_t \gets \max(f_t, f_{t - 1} + [a_j\geq mid])。检查是否有 2f_r - 1\geq \min(n, r) 即可。

时间复杂度 \mathcal{O}(n\log V)。代码。