浅谈与求前 k 优方案有关的问题

· · 算法·理论

前言

求前 k 优的方案有关问题，是一个常常被忽略的板块，似乎许多教学方法都不会将这类问题当成一个大板块来进行授课；选手接触这类问题的情境也各不相同。在第一次遇到这类问题时，常常无法想出正解，因为其实在太过套路。所以呕象决定写一篇专栏来为大家总结一下这类问题的方法！

常见形式

一般是这样的：

首先，我们要进行一个决策（通俗讲就是选择方案），就是选一些物品。题目会给出决策的权值。

决策的空间往往会非常大，可能是 O(n^2) 甚至是指数集。

题目的要求是求出权值前 k 优的所有决策的某个信息，k 的量级是可控的，在 [10^5, 10^6] 之间。

我就称这种问题是 k 优解问题。

我们来看一道例题：P1631 序列合并。

这道题的决策就是选择两个数 a_x,b_y，决策的权值就是 a_x+b_y，要求权值前 N 小的决策的权值。

又比如 P2541 [USACO16DEC] Robotic Cow Herd P，这题中的决策就是从 N 个位置中每个位置确定一个微控制器，权值就是选择的 P_{i,j} 之和。

通用方法

这一部分是初学者最难理解的一个部分。

我们需要设计的算法需要和 k 强相关，这意味这我们希望能够通过某种方法只会考虑到前 k 优的方案，并且做到不重不漏。

而具体的算法是这样的：

首先我们假设权值是一个数，更优的决策指的是权值更小的决策。

我们设计一种转换方案 f(S)，其中 S 是一种决策，f(S) 是一个决策集合，即对于 T\in f(S)，可以由 S 得到 T。

这非常地抽象，我们先把 f(S) 需要满足的性质列一下，我们称其为三要素。

首先，我们用一张图来刻画，图中每个节点表示一种决策，对于决策 S,T，若 T\in f(S) 则连有向边 S\rightarrow T。

  1. 我们找到最优决策 S_0，即 S_0 是所有决策中权值最小的一个。则 S_0 可以到达所有决策。这做到了不漏。

  2. 对于任何一个集合 T，S_0 到 T 的路径唯一。这做到了不重。

    • 前两条相当于图是一棵外向树。事实上也可以是外向森林。

  3. 对于决策 S 和 T，若有边 S\rightarrow T，则有 v(S)\le v(T)，其中 v(S) 表示决策 S 的权值。这有助于我们找到前 k 优的决策。

有了这张图，我们就可以和 dijkstra 一样，维护一个小根堆，每次取出小根堆的堆顶元素 S（即当前最优决策），然后将 S 连向的 T 全部加入。由于有第 3 个要素的限制，对于决策 S，只有当比它优的所有决策都被加入后，它才会被考虑。这样我们就可以在 O(k\log k) 的时间内得到前 k 优的决策。

在遇到这类问题时，知道牢记这三要素，就都可以套路地秒掉。

前两个要素往往同时考虑，相当于想一个变换规则，使得能够从 S_0 通过唯一方案变到任何一个决策。

例题

做法一：考虑这样的变换方案：对于决策 $(a_i,b_j)$，先把 $a$ 的下标从 $1$ 不断 $+1$ 到 $i$，然后再把 $b$ 的下标从 $1$ 不断 $+1$ 到 $j$。这显然满足前两条要素。而在下标变大的过程中，决策的权值肯定也变大，所以要素 $3$ 也能满足。这样就可以完成这道题了。 做法二：当然，我们可以构造一棵森林，即选择多个 $S_0$：将所有 $(a_i,b_1)$ 视为 $S_0$，然后变换就是把 $b$ 的下标 $+1$。 复杂度都是 $O(n\log n)$。 - [P2541 [USACO16DEC] Robotic Cow Herd P](https://www.luogu.com.cn/problem/P2541) 相当于上一题的数组变成了很多个，这时候我们构造森林就没用了，只能尝试扩展第一种做法。 首先，对于位置 $i$，将 $P_{i,j}$ 从小到大排序，那么 $S_0$ 就是每个位置选择 $P_{i,1}$。 然后对于一个决策 $S=(c_1,c_2,\dots,c_n)$，其中 $c_i$ 表示位置 $i$ 选择了 $P_{i,c_i}$。我们的变换方案就是：从 $S_0$ 开始，$i$ 从 $1$ 到 $n$ 依次遍历，将位置 $i$ 的选择从 $1$ 不断 $+1$ 到 $c_i$。这时候我们的决策可以用三元组 $(i,p,s)$ 表示，其中 $i$ 是当前的位置，$p$ 表示当前 $c_i=p$，$s$ 表示当前的权值。这样满足了三要素，可以通过此题。 这时候如果直接交是会 TLE 的。我们忽略了一个问题：**出度**。 我们的下一个考虑的位置可能是任意满足 $j>i$ 的位置 $j$，这样 $f(S)$ 的大小是 $O(n)$ 的，统计一个决策后会带来 $O(n)$ 的决策，复杂度是 $O(nk\log n)$ 的。 这时候我们就有一个实践时需要考虑的重要问题：**出度低复杂度化**。 常见的技巧是孩子兄弟表示法，对于父亲 $S$，将其儿子**按照权值大小排序**，分出兄弟关系，然后将连边改为父亲连向长兄，大哥连向二弟，$i$ 哥连上 $i+1$ 弟。这样每个点的出度都是 $O(1)$ 的，复杂度降为 $O(k\log n)$。 像这道题，出度是在改变 $i$ 的时候达到了 $O(n)$，我们只考虑这些儿子，这时候如果选择的下一个位置是 $j$，则增加的权值是 $P_{j,2}-P_{j,1}$，我们只需要按照这个将位置排序，决策 $(i,p,s)$ 的长兄就是 $(i+1,2,s+P_{i+1,2}-P_{i+1,1})$，$(i,2,s)$ 的弟弟就是 $(i+1,2,s-(P_{i,2}-P_{i,1})+(P_{i+1,2}-P_{i+1,1}))$。 - [P6646 [CCO 2020] Shopping Plans](https://www.luogu.com.cn/problem/P6646) 这是一个综合题。 容易发现，如果 $x_i=y_i=1$，这题就和上一题一模一样。 考虑如果只有一种商品该怎么做，设此时最少要选 $L$ 个，最多能选 $R$ 个，首先将商品按照价值从小到大排序。那么 $S_0$ 就是选前 $L$ 个。 如果 $L=R$ 的话，转移方案可以这样设计：对于决策 $(p_1,p_2,\dots,p_L)$，其中 $p_i$ 表示选择的第 $i$ 个被选商品的下标，且 $p_i$ 单调递增，我们从 $L$ 到 $1$ 遍历，依次将第 $j$ 个下标从 $j$ 不断 $+1$ 到 $p_j$，可以用四元组 $(i,now,nxt,s)$ 表示。其中 $i$ 是当前考虑的位置，$now$ 表示当前 $p_i=now$，$nxt$ 表示 $p_{i+1}=nxt$，因为 $p_i$ 不能越过 $p_{i+1}$，$s$ 表示当前权值。 如果 $L\neq R$，这相当于 $R-L+1$ 个 $L=R$ 的问题拼起来，构成一个森林，而森林的根的都是选最便宜的 $i$ 个，权值关于 $i$ 递增，直接连过去即可。 如果有多种物品呢，我们依旧可以套用上一题的做法。只不过每个位置是一个盲盒，我们移动下标的过程就是找到这个盲盒的后继，每个盲盒相当是一个动态的 $k$ 优解问题，这是一个 $k$ 优解问题的嵌套，依旧可以做，复杂度 $O((N+K)\log K)$。 ### 总结 到了这里，我们可以基本了解 $k$ 优解问题的基本形式，基本思路，和基本套路。以及一些基础的 $f(S)$ 构造方法。始终牢记三要素和出度低复杂度化，这些问题往往能够迎刃而解。 以上题目对于三要素的考察较为深入，我们可以加一个思考：在 [Shopping Plans](https://www.luogu.com.cn/problem/P6646) 这题中，如果 $c_i$ 存在负数，$f(S)$ 的设计会有什么变化？（只有一处细节会有调整，想想为什么那一处调整，而其它不调整）。 此外，对于出度低复杂度化，有时可能并不是那么直接（即找长兄和弟弟的过程），比如 [P2048 [NOI2010] 超级钢琴](https://www.luogu.com.cn/problem/P2048)，需要用数据结构找到长兄/弟弟。 $f(S)$ 的构造有时可能也不是很直接，因为第三条要素的限制实在是太强了，比如 [P12692 BZOJ3784 树上的路径](https://www.luogu.com.cn/problem/P12692)，前 $k$ 短的路径可以建立一个决策森林，但前 $k$ 长的路径可就没有办法了，我们无法仅通过删除从一个极长路径得到其它所有路径。这题用点分治的方法将路径的权值体现在序列上两数的和。 可能还有一些题呕象还是没见过的，欢迎大家在评论区交流心得，以及分享其它有关题目！ 写得这么认真，留个赞再走吧！ awa