浅谈一类前 k 小问题的另类做法

· · 算法·理论

本文主要记录了一类前 k 小问题的另一种个人认为适用性很广的做法，并且非常奇怪的是没什么人写这个做法（真的吗？），比如 Shopping Plans 一题，题解区的 12 篇题解均为使用堆维护决策的做法。

我不清楚这个做法是不是和用堆维护决策的那个做法本质相同，不过实现起来确实挺不一样的吧。我也不知道它有没有比较广为人知的名字，如果有的话可以提醒一下。

如果想看这类问题的主流解法推荐这篇文章，个人认为写的非常清晰且深刻。

先使用两个较为简单的问题举例说明这种做法大概是什么样子的。

以下均使用 V 表示答案的值域。

Example 1

给定一个序列 \{a_n\}，你需要选出一个 S\in \{1,2,\cdots,n\}，权值为其包含的所有元素的 a_i 之和，求权值前 k 小的 S。

Sol：

我们先二分答案，转而统计集合元素之和 \le \text{mid} 的 S 数量。

然后你发现正常的背包等做法都是不太好做的。但是我们并不是要求这样的集合的准确数量，只是要判断是否至少有 k 个就行了。因此考虑直接爆搜！

这个东西显然复杂度是对的，只要我们搜到 k 种方案就停下就行了。但是实现时需要保证一个非常重要的事情，就是 每次进入搜索都会新增至少一种合法方案。注意这个条件是非常严格的，换句话说，就是每次进入 dfs 函数都会导致计数器至少 +1。

具体实现大概是这样。

int cnt,k,a[maxn];
//sort a by ascending order
inline void dfs(int x,int sum)
{
    cnt++;if(cnt>=k)return;
    for(int i=x;i<=n;i++)
    {
        if(sum+a[i]>mid || cnt>=k)break;
        dfs(i+1,sum+a[i]);
    }
} 
inline int check(int mid){cnt=0;dfs(1,0);return (cnt>=k);}

需要将 a 升序排序的原因是，在下面的循环中会枚举下一个选中的位置，我们需要严格保证 每次枚举至少产生一种新的方案，否则将导致复杂度错误。

如果要输出前 k 小的话，如果我们二分出的第 k 小是 x，那么把权值 \le x-1 的方案搜出来输出，剩下的答案就一定全是 x 了。

Example 2

给定 n 个有序序列，第 i 个的长度为 l_i。定义一种方案为，从这 n 个序列中各选取一个元素，方案的代价为选取的元素总和。求权值前 k 小的方案。

Sol：

还是先二分，统计权值 \le \text{mid} 的方案数。

直接搜，难点还是保证每次至少搜到一种合法方案。

定义状态 (i,j) 为当前考虑到第 i 个序列，前 i-1 个序列选取的总和为 j。我们需要保证搜到这个状态时，能直接根据 i,j 的信息导出一个合法方案。不难想到，定义这个状态导出的方案为，将 i+1\sim n 的序列全部选择最小元素时的总和。显然这是在状态 (i,j) 的基础上尽可能最小化总和的方案，如果这个不合法那么状态 (i,j) 就是没用的，这样的状态也不会被搜到。

这样子就让计数器 +1 了，但是这个不是 (i,j) 能转移到的唯一状态，我们需要去枚举下一个 选取的元素不为最小值 的序列 k，然后去枚举这个序列选什么。

但是和上一个题一样的原因，我们必须保证枚举到的新状态都是有用的，否则多出来的这些冗余枚举会导致复杂度错误。

首先要保证枚举到的序列 k 至少产生一个有用状态，而序列 k 能贡献的最小元素是序列的次小值，因此要把 n 个序列按照次小值减最小值排序。

然后要保证固定序列 k 后，枚举的每一个元素至少产生一个有效状态，因此要把每个序列内部升序排序。

这样就能保证复杂度正确了。

Conclusion？

从上面两个例子中应该很容易了解这种做法的结构了。

我们先二分答案，转化为数 \le \text{mid} 的方案数，并判定是否 \ge k。

这样做的好处在于，我们不再要求所有方案按照权值升序被一个一个取出来，而只是从所有满足权值不大于某个值的方案集合中，以任意顺序选取直到达到 k 个。显然后者弱化了不少，可以直接搜。

可以发现这种做法的好处是不太需要脑子。

但是这个做法要求我们精细实现，用各种优化枚举的手段保证我们枚举到的状态数一定是不超过 k 的。

通常，按照某个指标排序就足以解决问题了。其实我觉得应该还存在需要用数据结构优化的例子，但是没找到对应的题（

感觉这种做法是一个高度套路化的模型，从思维上几乎没有任何难点，实现上有一定细节不过都是挺显然的步骤吧。

接下来是几个复杂一点的应用。

Example 3

在 Example 1 的基础上，要求 l\le |S|\le r，其余条件不变，求前 k 小的方案。

Sol：

略去二分及之前的步骤，默认数组已经升序排序。

我们可以考虑先搜出选取 l 个点的方案，然后在这个基础上去搜在后面选取至多 r-l 个点的方案。只要保证搜到 k 种方案就停下复杂度还是没有问题的。

对于前半部分，我们需要在状态里再记录一个 c，表示还有多少个数没选。但是如果你直接搜的话，当目前 |S|<l 的时候是无法直接贡献到答案里的，因此相当于我们枚举到了一个不能计入答案的状态，复杂度就爆了。（即使这个状态之后能变成合法状态还是会爆）

考虑沿用 Example 2 的想法，强行让状态 (i,j,c) 直接导出一个合法方案。我们的想法是，令这个状态直接导出这样一个方案，在 j 的基础上，再加上 [i,i+c-1] 这段区间的所有数。这个方案显然是剩下所有方案中最小的。

然后扩展状态的话，就考虑上面那个东西的反面，即枚举一个 k，表示 [i,i+c-1] 这段区间第一个没选的位置，直接转移即可。

我们需要保证每次枚举 k 后都能至少导出一个合法方案。可以观察到 k 越靠后，转移到的状态越容易存在至少一个合法方案（和越小）。所以倒序枚举 k，当目前转移到的状态无法导出合法方案了就 break 即可。

这样就做完了前半部分。对于后半部分，可以发现是只限制了 |S| 大小上界的 Example 1。这东西没什么实质性影响，记录一个 cnt 直接搜，太大了就停下即可。

P6646

即开头所提到的 Shopping Plans。

笔者为了验证自己的想法，用这个做法写了一下，发现过了，所以应该是没问题的。

如果 m=1，即物品没有分类的话就是 Example 3。

我们考虑直接用上面的做法，对每类物品搜出其能取到的值的集合，最后在这若干个集合中各取一个相加求第 k 小，也就是 Example 2。

但是问题并没有这么简单，实现起来有诸多细节。

比如，你不能对每类物品分别搜 k 种可能取到的值出来，这样单次 check 复杂度将达到 O(mk)。

但是我们可以做一些剪枝。显然，对于第 i 类物品，其可用的值应当满足，当其它类物品全部取其可能取到的最小值时，总和不超过限制的 \text{mid}。

然后发现，如果第 i 类物品有 c_i 种可能的这样的值，那么总共合法的方案数至少为 \sum (c_i-1)。这是因为上面描述的就已经提供了 c_i 种方案了。减一是重复计算了所有类都取最小可能值的情况。

也就是说，我们对每类分别搜，总方案数到达 m+k 就可以停下了。这样就把所有可能取到的值的总数控制在了一个可以接受的范围。

我的实现很丑，没啥参考价值，不过还是贴一下。qoj submission。