子集第 k 小和

排序正数子集和;用唯一父状态堆枚举,每个状态只生成替换末尾下标和追加下一下标两个后继。

标签 第k小 / 子集和 / 堆 / 枚举

问题形式

给定长度为 𝑛 的正整数序列 𝑎1≤…≤𝑎𝑛。对每个下标集合 𝐼⊆{1,…,𝑛},定义子集和

𝑤(𝐼)=∑𝑖∈𝐼𝑎𝑖.

求所有 2𝑛 个子集和中第 𝑘 小的值,并输出对应方案。

1≤𝑛,𝑘≤106。

模型

把子集写成递增下标序列。空集是根状态,值为 0。

对非空子集 𝐼,令 𝑗 为最大下标。定义父状态:

  • 若 𝑗=1,父状态为空集;
  • 若 𝑗−1∈𝐼,父状态为 𝐼∖{𝑗};
  • 若 𝑗−1∉𝐼,父状态为 (𝐼∖{𝑗})∪{𝑗−1}。

父状态的值不大于 𝐼 的值:删除最大下标会减小,替换 𝑗 为 𝑗−1 只增加 𝑎𝑗−𝑎𝑗−1≥0。

反过来,若 𝐼 的最大下标为 𝑗<𝑛,它只有两个子状态:

𝐼∪{𝑗+1},(𝐼∖{𝑗})∪{𝑗+1}.

空集的唯一子状态是 {1}。

这两个转移正好是“把末尾下标加一”和“追加下一个下标”。

正确性

每个非空子集都有唯一父状态,因此所有子集被组织成一棵以空集为根的树,每个非空子集只出现一次。

父状态的值不大于子状态的值,因此可以用 唯一父状态堆枚举:初始把空集放入小根堆,每次取出堆顶并把它的两个子状态加入堆。第 𝑘 次取出的就是第 𝑘 小子集和。

复杂度

排序为 𝑂(𝑛log𝑛);堆中保留 𝑂(𝑘) 个状态,每个状态只生成两个后继,时间为 𝑂(𝑛log𝑛+𝑘log𝑘),空间为 𝑂(𝑛+𝑘)。

源码位置