子集第 k 小和
排序正数子集和;用唯一父状态堆枚举,每个状态只生成替换末尾下标和追加下一下标两个后继。标签 第k小 / 子集和 / 堆 / 枚举
问题形式
给定长度为 的正整数序列 。对每个下标集合 ,定义子集和
求所有 个子集和中第 小的值,并输出对应方案。
。
模型
把子集写成递增下标序列。空集是根状态,值为 。
对非空子集 ,令 为最大下标。定义父状态:
- 若 ,父状态为空集;
- 若 ,父状态为 ;
- 若 ,父状态为 。
父状态的值不大于 的值:删除最大下标会减小,替换 为 只增加 。
反过来,若 的最大下标为 ,它只有两个子状态:
空集的唯一子状态是 。
这两个转移正好是“把末尾下标加一”和“追加下一个下标”。
正确性
每个非空子集都有唯一父状态,因此所有子集被组织成一棵以空集为根的树,每个非空子集只出现一次。
父状态的值不大于子状态的值,因此可以用 唯一父状态堆枚举:初始把空集放入小根堆,每次取出堆顶并把它的两个子状态加入堆。第 次取出的就是第 小子集和。
复杂度
排序为 ;堆中保留 个状态,每个状态只生成两个后继,时间为 ,空间为 。