奇偶子序列题解

思路

固定一个候选上界 $x$。原问题可以转化为判定：能否选出长度至少为 $k$ 的子序列，使其奇数位置全部不超过 $x$，或者使其偶数位置全部不超过 $x$。

分别考虑这两种位置。扫描原数组并维护已经选出的元素个数。当下一个子序列位置受到限制时，只能选择不超过 $x$ 的元素；当它不受限制时，直接选择当前元素总不会变差。这个贪心会尽可能早地完成每一次选择，因此若它不能得到 $k$ 个元素，任何其他选择也不能得到。

可行性关于 $x$ 单调：某个 $x$ 可行时，更大的值也一定可行。因此可以二分最小可行值。

做法

写一个判定过程，参数表示受限制的是奇数位置还是偶数位置。顺序扫描数组；若下一个位置不受限制，直接计入，否则仅在当前值不超过 $x$ 时计入。任一模式最终计数达到 $k$，就说明 $x$ 可行。

在 $[1,10^9]$ 上二分。若中点可行就收缩右端点，否则提高左端点，最终得到最小代价。

贪心正确性可由交换论证得到：在扫描到任意前缀后，贪心选出的同样数量元素的末尾位置不晚于任意合法方案。对于不受限制的位置，立即选择显然最早；对于受限制的位置，选择遇到的第一个合法元素同样最早。归纳后，贪心能选出的元素数不会少于任何合法方案。

复杂度

每次判定扫描数组两遍，时间复杂度为 $O(n)$，二分次数为 $O(\log 10^9)$，总时间复杂度为 $O(n\log 10^9)$。除输入数组外只使用常数额外空间，总空间复杂度为 $O(n)$。