题解 | #小红的数组清空#

本题的核心在于序列覆盖（Sequence Covering）。 我们需要将数组中的所有元素划分为若干个形如 的连续递增子序列。 每一个子序列的“头部”（第一个元素）需要花费 1 的代价进行删除，而该子序列后续的所有元素（）都可以利用规则“免费”删除。 因此，最小化总代价等价于最小化划分出的连续递增子序列的数量。

频率差分与贪心法

我们将问题转化为对每个数值“流”的处理：

• 假设数值 在数组中出现了 次。这意味着有 个以 结尾的“活跃链条”，这些链条都有资格接纳 为下一个元素。

• 假设数值 在数组中出现了 次。

• 我们对比 和 ：

  • 情况 A： 说明当前的 元素较少，完全可以全部接在 的后面。所有的 都能免费删除，不需要开启新链条。代价增加 0。 (注：多余的 链条在此处终止，不再延伸)。
  • 情况 B： 说明当前的 元素太多了， 提供的“接口”不够用。我们尽可能将 接在 后面（接纳 个），剩下 个 无法找到前驱，必须作为新链条的头部，每个需花费 1 代价。 代价增加 。

• 特殊情况：如果 不存在（即 ），则所有 都必须开启新链条。这符合公式 。

综上所述，总代价计算公式为：