CF2117C Cool Partition 题解

· · 题解

不难想到贪心策略：对于每个位置，如果可以断开必定断开。

证明：假设当前位置为 i 且可以断开。如果最优方案是在位置 j（j>i）断开的话，我们可以将位置 [i+1,j] 并入下一段内。

根据我们的假设，这样做一定是合法的，并且由于当前段中的元素变少了，我们的总段数也一定不会变少。

最后一段是否合法也不影响，因为如果不合法，我们可以简单地将其并入前面一段，这样做不会影响总段数。

考虑实现，可以开两个 set，一个存前一段中的元素（记作集合 A），一个存当前段中的元素（记作集合 B）。

遍历到 a_i 时，将其从 A 中移除，并将其加入 B。当 A 为空时，即意味着可以从当前位置断开，此时更新答案并将 B 作为新的 A 继续遍历。

时间复杂度 O(n \log n)。

CF 提交记录