多集合第 k 小和
每个集合选一个数,求和第 k 小;压缩最近一个非首项,按唯一父状态堆枚举,集合按首增量排序。标签 第k小 / 堆 / 枚举 / 多集合
问题形式
给定 个非空正整数集合 。从每个集合中选出一个数,一种方案的价值为选出的数之和。求所有方案中第 小的价值,并输出方案。
集合总大小不超过 ,。
模型
先把每个集合升序排序,并去掉大小为 的集合:它们的选择固定,直接把唯一的数加入公共常数。
对剩下的集合重排,使
非降。记第 个集合为 ,大小为 。
所有集合都选第 项时是根状态。一个堆状态写成 :
- 是当前总和;
- 是最后一个选择下标大于 的集合;
- 是第 个集合选的下标,。
第 个集合之后的集合都选第 项;更早的选择已经包含在 中。根状态用 表示。
状态 的后继有三种:
若 且 ,推进当前集合:
若 ,切换到下一个集合,并选它的第 项:
若 、 且 ,把当前集合退回第 项,同时把下一个集合提到第 项。记
则后继为
第三条转移是“反悔”:它把当前集合的第一次增量 撤回,换成下一个集合的第一次增量 。因为集合已按 升序排列,所以三种转移都不会减小价值。
正确性
任意非根方案都有唯一的父方案:找到最后一个下标大于 的集合,若它的下标大于 ,父方案就是把该下标减一;若下标等于 ,父方案由前一个集合的状态恢复。第三条转移正好覆盖“当前集合回到第 项”的情形。因此这些状态组成一棵以全选第 项为根的树。
每个父状态的价值不大于子状态,于是可以用 唯一父状态堆枚举。初始把根状态放入小根堆,每次取出堆顶并加入它的全部后继;第 次取出的就是第 小价值。
复杂度
集合内部排序与按 排序共 ;堆中保留 个状态,每个状态至多三个后继,时间为 ,空间为 。