Liveddd's Blog

愛にできることはまだあるかい

[ARC148E] ≥ K

还行的数数题,感觉并不难。

在 $n\le 2\times 10^5$ 的情况下,我们似乎很难去设计 DP 状态。考虑从别的角度思考。

考虑限制的条件,发现:

  1. 不存在相邻的 $x\le \frac{k}{2}$。
  2. 若 $x\le \frac{k}{2}$,则 $y\ge \frac{k}{2}$,需满足 $\frac{k}{2}-x\le y-\frac{k}{2}$。

注意第二个条件我们不好处理。我们考虑将所有数按照 $|x-\frac{2}{k}|$ 从大到大排序,若相同我们将大的排在前面。尝试按照这个顺序依次插入,这样我们始终在满足条件一的前提下始终满足条件二。过程中我们只能插在两个 $x\ge \frac{k}{2}$ 的数中间,我们维护这样的位置即可。注意到中间可能会有数值相同的数,但是答案中视作相同,所以我们乘上逆元即可。时间复杂度 $\mathcal O(n\log n)$,瓶颈在于排序。

其实实现的时候可以直接按照 $x$ 从大到小排序,然后用双指针分别从首尾扫。