多集合第 k 小和

每个集合选一个数,求和第 k 小;压缩最近一个非首项,按唯一父状态堆枚举,集合按首增量排序。

标签 第k小 / 堆 / 枚举 / 多集合

问题形式

给定 𝑛 个非空正整数集合 𝐴1,…,𝐴𝑛。从每个集合中选出一个数,一种方案的价值为选出的数之和。求所有方案中第 𝑘 小的价值,并输出方案。

集合总大小不超过 106,𝑘≤106。

模型

先把每个集合升序排序,并去掉大小为 1 的集合:它们的选择固定,直接把唯一的数加入公共常数。

对剩下的集合重排,使

𝑑𝑖=𝐴𝑖,2−𝐴𝑖,1

非降。记第 𝑖 个集合为 𝐴𝑖,大小为 𝑚𝑖。

所有集合都选第 1 项时是根状态。一个堆状态写成 (𝑣,𝑖,𝑗):

  • 𝑣 是当前总和;
  • 𝑖 是最后一个选择下标大于 1 的集合;
  • 𝑗 是第 𝑖 个集合选的下标,𝑗≥2。

第 𝑖 个集合之后的集合都选第 1 项;更早的选择已经包含在 𝑣 中。根状态用 𝑖=𝑗=0 表示。

状态 (𝑣,𝑖,𝑗) 的后继有三种:

  1. 若 𝑖>0 且 𝑗<𝑚𝑖,推进当前集合:

    (𝑣+𝐴𝑖,𝑗+1−𝐴𝑖,𝑗,𝑖,𝑗+1).
  2. 若 𝑖<𝑛,切换到下一个集合,并选它的第 2 项:

    (𝑣+𝐴𝑖+1,2−𝐴𝑖+1,1,𝑖+1,2).
  3. 若 𝑖>0、𝑗=2 且 𝑖<𝑛,把当前集合退回第 1 项,同时把下一个集合提到第 2 项。记

    Δ=(𝐴𝑖+1,2−𝐴𝑖+1,1)−(𝐴𝑖,2−𝐴𝑖,1),

    则后继为

    (𝑣+Δ,𝑖+1,2).

第三条转移是“反悔”:它把当前集合的第一次增量 𝑑𝑖 撤回,换成下一个集合的第一次增量 𝑑𝑖+1。因为集合已按 𝑑𝑖 升序排列,所以三种转移都不会减小价值。

正确性

任意非根方案都有唯一的父方案:找到最后一个下标大于 1 的集合,若它的下标大于 2,父方案就是把该下标减一;若下标等于 2,父方案由前一个集合的状态恢复。第三条转移正好覆盖“当前集合回到第 1 项”的情形。因此这些状态组成一棵以全选第 1 项为根的树。

每个父状态的价值不大于子状态,于是可以用 唯一父状态堆枚举。初始把根状态放入小根堆,每次取出堆顶并加入它的全部后继;第 𝑘 次取出的就是第 𝑘 小价值。

复杂度

集合内部排序与按 𝑑𝑖 排序共 𝑂(𝑁log𝑁);堆中保留 𝑂(𝑘) 个状态,每个状态至多三个后继,时间为 𝑂(𝑁log𝑁+𝑘log𝑘),空间为 𝑂(𝑁+𝑘)。

源码位置