【做题笔记】洛谷P5584 【SWTR-01】Sunny's Crystals

Problem

P5584 【SWTR-01】Sunny's Crystals

题目大意：

给你一个长度为 \(n\) 的序列，每次可以删掉下标为 \(2\) 的非负整数次幂的数，删掉一个数后他后面的数会往前补，问删掉所有值为 \(w\) 的数所需要的最小步数及对应的方案。

Solution

考虑贪心做法。

如果当前能删的数中有 \(w\)，显然删 \(w\) 最优。但当有多个值为 \(w\) 的位置时应该如何选择？容易发现删最后一个更优，因为删前面的数会影响后面的数，所以要尽量不影响后面。
如果当前能删的数中没有 \(w\)，那么与之前相反，要让尽可能多的位置改变，所以删第一个数。

但是直接做是 \(n^2\) 的，所以考虑优化。
这里给出一个不需要数据结构的做法。
考虑到能删的位置只有 \(\log n\) 个，所以可以维护 \(\log n\) 个指针，分别指向能删的位置。每次删一个数就把当前及之后的指针右移一位。并且在删过的数上打上 tag。每次删数都只会影响 \(\log n\) 个指针，且每个数最多被 \(\log n\) 个指针扫到，复杂度为 \(O(n \log n)\)。

Code

实现起来很简单，码就不贴了。