BalticOI 2021

A.A Difficulty Choice

蓝题做不出来？蓝题做不出来？蓝题做不出来？

发现要求是这 \(k\) 个数和在 \([A,2A]\) 之间，这个 \(2A\) 肯定有说法。

分类讨论有没有选择 \(\geq A\) 的数。如果选择了，一定是仅选择一个 \(\geq A\) 中最小的数，这时已经满足 \(\geq A\) 了，剩下的肯定是要取前 \(k\) 小。

如果没有选择，那么先默认选择最小的 \(k\) 个数，如果和 \(<A\)，就不断把最小的数换成 \(<A\) 的数中最大的数，这样每次的变化量都小于 \(A\)，不会突然超过 \(2A\) 的上界限制。

要先找到第一个 \(\geq A\) 的数的下标 \(i\)，还要知道下标在 \([1,k]\) 和 \([i-k,i-1]\) 中的数的值，总询问次数 \(\log n+2k\)。