问题分析 题目要求我们找到前 K 小的可行购物计划的代价。每个购物计划需要满足对于每种商品类型 j，选中的商品数量在 [xj​,yj​] 之间。我们需要高效地生成这些计划并按代价从小到大输出。 关键思路

​预处理​：

对每种商品类型的商品按价格排序。 计算每种商品类型的最小必要选择（即至少选 xj​ 个最便宜的商品）。 检查是否存在可行解（即是否每种商品类型的 xj​≤yj​）。

​初始解​：

初始解是选择每种商品类型恰好 xj​ 个最便宜的商品，计算总代价。

​生成后续解​：

使用优先队列（最小堆）来维护当前的最小代价解。 每次从堆中取出最小代价的解，然后生成可能的“相邻”解（即通过替换或增加商品来生成新的解）。 通过动态扩展状态，确保每次生成的解都是当前未考虑的最小代价解。

​状态扩展​：

对于每种商品类型，考虑替换一个已选商品为更贵的商品，或者增加一个未选商品。 通过优先队列确保每次扩展的都是当前最小代价的解。

复杂度分析

​预处理​：排序每种商品类型的商品，时间复杂度为 O(M⋅NlogN)。 ​优先队列操作​：每次操作的时间复杂度为 O(logK)，最多进行 O(K) 次操作，因此总时间复杂度为 O(KlogK)。 总体时间复杂度为 O(M⋅NlogN+KlogK)，能够处理题目中的约束条件。

总结 通过贪心算法和优先队列的结合，我们能够高效地生成前 K 小的购物计划。预处理确保初始解的可行性，优先队列的动态扩展保证了每次生成的解都是当前最小代价的解。这种方法避免了暴力枚举所有可能的解，显著提高了效率。