日记 - 伊埃斯的博客站

昨天晚上睡得实在是太晚了，然后中午玩爹 5 弘文过头了，直接睡了一下午。

Serval and Colorful Array (Easy Version)↗

感觉这题不值 2600。~~虽然我还是没做出来~~

我们考虑一个字串怎么来。显然最优的情况是中间的一个数不动，然后两旁的挪过来。我们枚举每个可能的中间的数 $a_{pos}$ ，然后对于 $\forall i \in [1,k]$ ， $O(n)$ 处理 $l_i,r_i$ 分别表示左边离 $pos$ 最近的 $i$ 离 $pos$ 多远，右边离 $pos$ 最近的 $i$ 离 $pos$ 多远。现在的问题就是，如何选择使得 $\frac{k}{2}$ 个 $l_i$ 和 $\frac{k}{2}$ 个 $r_i$ 加起来最小。我们先钦定都选左边的，答案就是 $\sum\limits_{i = 1}^{k}l_i$ ，再记录一个 $c_i = r_i - l_i$ ，我们将 $c$ 从小到大排序，最终的答案就是 $\sum\limits_{i = 1}^{k}l_i + \sum\limits_{i = 1}^{\frac{k}{2}}c_i$ 。别忘了减掉多算的 $\sum\limits_{i = 1}^{k}|i - \lceil\frac{k}{2}\rceil|$ 。

后日谈

做又臭又长的世界任务，刚刚被新地图震撼，一看锚点数量直接原地爆炸。

不管了，做什么世界任务，做题！

Thanks for reading!

日记

周日 3月 30 2025

289 字 · 2 分钟

life 日记