[ARC131D] AtArcher 题解

题意

数轴上有一个箭靶以 \(0\) 为轴心左右对称，给定每个得分区域的范围和分值，要求射 \(N\) 支箭在靶上，且任意两支箭的距离不少于 \(D\)，求最大得分。保证从中心向两侧分数不增。特别的，如果有一只箭射在了分界点上，以较大得分为准。

思路

由于分数的单调性，我们肯定会让两只相邻的箭之间的距离恰好为 \(D\)，即达到最紧密的情况。

我们设中心箭的定义为左边（不含自己）有 \(\lfloor\dfrac{N}{2}\rfloor\) 支箭，右边（含自己）有 \(\lceil\dfrac{N}{2}\rceil\) 支箭。那么中心箭的范围只可能是 \((-D,D)\)（因为再往外移就相当于将最左/右边的一支箭射到了最右/左边，由于对称性，这样肯定不会更优）。

考虑枚举中心箭的位置，那么剩余箭的位置可以直接算出来，于是我们就有了一个优秀的 \(O(ND)\) 的做法。

还是过不去，考虑优化。可以发现，在中心箭由 \(-D+1\) 移到 \(D-1\) 的过程中，任意两个相邻分数的分界点最多被跨越两次（因为两只箭之间的间隔为 \(D\)）。而且每只箭模 \(D\) 同余，因此，我们可以对模 \(D\) 的余数相等的分界点分成一组，然后每次移动时暴力扫描看哪些分界点被跨越了，更新答案即可。时间复杂度 \(O(D+N)\)。