Luogu6646 [CCO2020] Shopping Plans

题意： 商店里有 个物品，每个物品有种类与价格。

对于第 个种类，需要购买商品的个数在 之间。

求出前 便宜的方案的价钱，或指出不存在。

，时限 。

---

Part0

先介绍解决这类“前 优”问题的一个通用思路。

我们考虑方案与方案之间的转移。

对于方案 ，记 为 的后继方案集合（具体定义暂不明确）。

我们按以下流程求解问题。

• 将花费最小的方案加入小根堆中

• 重复执行直到堆为空，或已得到所有答案

  • 将堆顶方案 输出并弹出

  • 将 中的各个方案加入堆中

考虑怎样设计 才能使得这个算法正确。

将 向 连边，形成一张有向图。

• 所有方案形成一棵以花费最小的方案为根的外向树。

  这保证了不重不漏。

• 的权值都大于等于 的权值。

这样，不难证明前 优的方案构成一个包含根的联通块。我们前述的算法可以找出这个联通块。

Part1：

将物品按照价格从小到大排序，花费最小的方案是选择最左的 个物品。

我们按如下的方法构造 ：

• 将最左的能右移的物品右移若干，但不能跨越其他已选的物品。

不难发现，这样调整之后权值必然变大，且得到所有方案的方法数恰都为 。符合我们的要求。

如图是一个方案对应的调整方法。

观察： 在任意时刻，一定是前面有一个前缀是紧密连续的，然后将这个前缀的末端向右移若干。

美中不足的是，单个 集合的大小可能达到 ，不能保证复杂度。

我们改而让物品每次只能右移一位，并加入当前物品的概念，将 改为：

• 将当前物品改为紧密前缀的末端（最靠左的能右移的物品）。

• 将当前物品右移一位。

不难发现这两种 是等价的。“当前物品的连续移动”对应前文“将最左的能右移的物品右移若干”。

形式化地，记 表示前缀 还没有动，当前物品位于 ，当前物品右侧的物品位于 的方案。

转移： 或 。分别对应“移一步”与“ ‘当前物品’前移然后移一步”。

Part1.5：

只需要稍作修正，对于初始未移动的前缀 ，钦定其可以转移到 （多选一个）即可。

Part2：

最优方案是每个种类选择最小的。

按如下的方法构造 ：

从前往后考虑种类，记当前种类为 。

• 将种类 所选的数右移一位。

• 将 后移若干，再将种类 所选的数右移一位。

可惜，单个 集合的大小不能保证。

原先的 的结构形如图上半部。

我们将儿子的权值从小到大排序，然后将儿子串起来（如图下半部），即可将度数变小。

在本题中，我们将种类按照 最小值与次小值的差 从小到大排序，然后如此构造 ：

• 将种类 所选的数右移一位。

• 将 后移一位，再将种类 所选的数右移一位。

• 若 所在种类目前选择次小值，则恢复为最小值。然后将 后移一位，再将种类 所选的数右移一位。

  （我们的排序能保证这一步权值不降）

  这一步具体的情形如下图：

  

Part3：一般情况

考虑 Part1.5 中的算法，其实就是将 的问题变成了一个黑箱，支持 得到下一个最优的解。

观察 Part2 中的算法，其实就是维护 个黑箱（排好序的数组），操作中只需要访问黑箱的下一个解。

将这两个算法配合起来即可 解决本题。