集合选数最值一类问题
一共有两种类型，我分别介绍。
类型一
先来看一道简单的题目：
给你$m$个序列，每个序列有$n$个非负整数，你现在要在每个序列选一个数，这一共有$n^m$种方案，一种方案的值定义为所选的数的和，要你输出值最小的$n$种方案的和。
数据范围： $0 \lt m \le 100$, $0 \lt n \le 2000$。
先考虑$m = 2$的情况，一共有$n ^ 2$种方案，设两个序列为$a, b$，假设我们已经把它们排好序了，即$a_i \le a_{i+1} \ (1 \le i \lt n)$, $b_i \le b_{i+1} \ (1 \le i \lt n)$。方案$f(i, j)$的值为$a_i + b_j$。$f$有以下性质：$f(i, j) \le f(i, k) \ (j \lt k)$，$f(i, j) \ (1 \lt j \le n)$如果是最后的答案，那么$f(i, j - 1)$肯定也是答案。我们只需要维护一个优先队列，初始时将$f(i, 1)$加入优先队列，从优先队列中第$k$次取出的$f(i, j)$即为第$k$小的方案，每次取出后，若$j \lt n$，把$f(i, j + 1)$加入优先队列。时间复杂度为$O(nlog_2{m})$
至此，我们有了$m = 2$的合并算法，当$m \gt 2$时，我们只需要将$m$个序列进行$m - 1$次合并。得到的即为答案。总的时间复杂度为$O(mnlog_{2}m)$，可以通过此题。
我们考虑与此题类似的一个问题，给定$n$个多重集合$c_i$，第$i$个集合的大小为$s_i$，要在每个集合中选一个数，一种方案的值定义为所选的数的和（或积），求第$k$大（或小）的方案的值。
对于此问题上面这个做法还不够优秀。
以下介绍第一种更为优秀的做法。
以求第$k$大为例。
先把集合内元素排序，再以集合的最大值与次大值的差作为关键字对集合进行排序，即对于集合$i$满足$s_{i, j} \le s_{i, j + 1}, \ s_{i, 1} - s_{i, 2} \le s_{i + 1, 1} - s_{i + 1, 2}$ (如果某个集合只有一个元素，那么这个集合只有一种选法，就可以不用考虑了)。
把上面$f$的维数扩展到$n$维，$f(p_1, p_2, \cdots , p_n)$代表一个方案，第$i$个集合选了第$p_i$大的数。每个集合默认选择最大的数，这种选择作为初始方案，再进行逐个集合更改所选的数。我们只需要记录当前待选择的集合的编号$i$，当前集合所选的数第$j$大的数，以及当前方案的值。之前的选择$p_1, p_2, \cdots p_{i - 1}$，完全可以丢弃，$p_{i + 1}, p_{i + 2}, \cdots p_n$默认都是选择最大的，也不用记录，所以$f$只有三维$(i, j, sum)$。
对$f(i, j, sum)$的后继进行定义：
若$j \lt c_i$，$f(i, j + 1, sum - s_{i, j} + s_{i, j + 1})$是它的后继；
若$i \lt n$，$f(i + 1, 2, sum - s_{i + 1, 1} + s_{i + 1, 2})$是它的后继；
若$j = 2 \ \&\& \ i \lt n$，$f(i + 1, 2, sum + s_{i, 1} - s_{i, 2} - s_{i + 1, 1} + s_{i + 1, 2})$是它的后继；
相应的，我们定义前驱。
我们把每种方案看成一个节点，它与它的后继之间的边为后继边，它与它的前驱之间的边为前驱边。
存在以下性质：
$f(i, j, sum)$不小于它的后继，不大于它的前驱。
因为前面我们对集合进行了排序，
满足$s_{i, j} \ge s_{i, j + 1}$，所以第一种和第二种后继（如果存在）存在这种性质。
满足$s_{i, 1} - s_{i, 2} \le s_{i + 1, 1} - s_{i + 1, 2}$，所以第三种后继（如果存在）存在这种性质。$f(i, j, sum)$可以有多个后继，但只有唯一的前驱。
因为我们是逐位更改的，当前集合和所选的数的不同，这两种方案通过后继边所能达到的方案不会有交。对于任意合法的方案最终一定能通过前驱边到达初始方案。
即从最初方案通过后继边可以到达任意合法方案。
这很显然。
那么这就是一棵树。如果一种方案成为答案，那么它的前驱肯定也是答案。那么我们可以维护一个优先队列，存当前可能成为答案的方案，第$k$个答案即为优先队列第$k$次的最大值，一种方案出队后把它的所有后继加入优先队列。
事实上，这种结构只要是一个$DAG$，就可以用优先队列维护了，只不过可能要去重。
这个算法的时间复杂度为$O(nlog_{2}n + \sum_i^n{c_ilog_{2}c_i}+ klog_{2}mk)$，其中$m$为每种方案的平均后继个数。由于$m$是常数，可以忽略，那么时间复杂度就是$O(nlog_{2}n + \sum_i^n{c_ilog_{2}c_i}+ klog_{2}k)$。这个算法是相当优秀的。
类型二
假设我们始终在一个集合内选数，即给你一个有$n$个元素的多重集合$s$，选$m$个不同的数定义为一种方案，求第$k$大（或小）的方案的值。
利用上面的算法的思想，$f(p_1, p_2, \cdots , p_m) \ (1 \le p_1 \lt p_2 \lt \cdots \lt p_m \le n)$为一种方案。
定义后继：如果$f(p_1, p_2, \cdots , p_i + 1, \cdots , p_m)$合法，那么它为$f(p_1, p_2, \cdots , p_m)$的后继。
类似的定义前驱。
但是这是一个DAG，如果这样直接用优先队列做，需要去重。
我们再次利用逐位更改的思想，多加一维$i$，表示$p_{i + 1}, \cdots , p_m$不会更改。
$f(i, p_1, p_2, \cdots , p_i, \cdots , p_m)$的后继有：
如果$f(i, p_1, p_2, \cdots , p_i + 1, \cdots , p_m)$合法，那么它为$f(i, p_1, p_2, \cdots , p_m)$的后继。
如果$f(j, p_1, p_2, \cdots , p_j + 1, \cdots , p_m) \ (1 \le j \lt i)$，那么它为$f(i, p_1, p_2, \cdots , p_m)$的后继。
显然它也有上面的三个性质。
那么这就是一颗树了，可以直接用优先队列做，不需要去重了。
给出$n$个整数$a_1, a_2, \cdots , a_n$，问从中选$m$个数乘积第$k$大是多少。
数据范围：$1 \le n,k \le 10000$, $1 \le m \le13$, $k \le C^n_m$, $-10^6 \le a_i \le10^6$。
假如求的是数和的第$k$大，或正整数的乘积第$k$大是多少，那么可以直接用上面的那个算法。
但是所选的负数的个数或影响乘积的正负，所以我们枚举$m$中选的负数的个数。如果负数个数为偶数，这类方案的乘积非负，选择求绝对值前$k$大的乘积。反之，这类方案的乘积非正，选择求绝对值前$k$小的乘积。
参考资料
POJ2442 Sequence
第十三届北航程序设计竞赛预赛
第十三届北航程序设计竞赛预赛题解
LibreOj #6254. 最优卡组
Sgu 421. k-th Product
bzoj 1425: SGU 421 k-th Product
Sengxian’s Blog
ZJOI2010讲课