题目

{% fold 点击显/隐题目 %}

蕊蕊有n部喜欢的番剧，每部番剧里面有m个妹子，每个妹子都有一个颜值。现在蕊蕊想从每部番剧里挑出一个妹子，总共挑出n个妹子，组成后宫团，后宫团的颜值是里面n个妹子的颜值和。显然，蕊蕊一共可以组成m^n个后宫团，现在她想知道这m^n个后宫团中，颜值和第K大的总颜值是多少。 若K>m^n，输出0

蕊蕊一共可以组成3^2=9个后宫团，总颜值分别是：
1+2=3,1+2=3,1+5=6
4+2=6,4+2=6,4+5=9
3+2=5,3+2=5,3+5=8
其中第4大的是6

第一行三个整数n,m,k(1<=n<=1000,1<=m<=500,1<=k<=1000)。 接下来n行，每一行表示一部番剧的信息。每行m个整数，表示该番剧里m个妹子的颜值a(1<=a<=100000)。
输出一个整数，表示颜值和第K大的后宫团总颜值。
2 3 4 1 4 3 2 2 5
6
{% endfold %}

题解

直接看的话很容易想到01背包第k大
但是显然时间复杂度会爆炸
这里应该使用多路归并

按照01背包的思路,我们可以一组一组来看
给每一组从大到小排序
然后将两组合并到一起
这样,当将所有的都合并进来后,得到的数组就是前k大

问题转换为将 a b 两个数组按照a+b合并到一起
如果枚举计算出所有的a+b显然时间复杂度太高
而且当数组很大的时候,其实很多a+b的计算是完全没有意义的


如图,对于前5大,只有绿色部分是有用的

但是,对于前k大,我们计算两个数组前√k个的和显然又是不行的
可以通过使用优先队列来满足我们的要求

我们以任意一列为基准,记录下用这一列的数分别加上另一列最大的数,插入到优先队列中
这时优先队列里的最大值(队列最前的值)必然是所有结果中最大的那一个值
将其插入到我们的结果数组中,然后从优先队列中删除它
对于第二大的值,可能是a[1]+b[0]也有可能是a[0]+b[1]
因此我们还应该通过刚刚的a[0]+b[0]得到a[0]+b[1]插入到优先队列中
……

以此类推,当最大值是a[i]+b[j]时,我们要将a[i]+b[j+1]插入到队列中
(由于a[i]+b[j]是最大值,那么可以得知a[m]+b[n] (m<=i n<=j)已经从队列中删除,也即a[m]+b[j]已经插入到队列中)
此时优先队列中的最大值必然是下一个最大值

每次出队一个入队一个
总共出队k次
再加上优先队列本身的复杂度O(log(n))
总复杂度是 O(klog(n))

整道题复杂度为O(mklog(n)) 是一个可以接受的复杂度

代码

{% fold 点击显/隐代码 %}```cpp 蕊蕊的后宫团 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
#include
#include
#include
#include
#include
using namespace std;

const int maxn = 5005;
const int maxm = 505;
const int maxk = 2005;

int a[maxn][maxm];
int n, m, k;
int len;

bool compare(int a, int b) { return a > b; }

struct node {
int s, b;
node(int _s, int _b) : s(_s), b(_b) {}
bool operator<(node a) const { return a.s > s; }
};

void merge(int *a, int *b, int *c) {
priority_queue Q;
for (int i = 0; i < len; i++)
Q.push(node(a[i] + b[0], 0));

len = 0;
for (int i = 0; i < k && !Q.empty(); i++) {
    ++len;
    node r = Q.top();
    Q.pop();
    c[i] = r.s;
    int t = r.b;
    if (t + 1 < m)
        Q.push(node(r.s - b[t] + b[t + 1], t + 1));
}

}

int main() {
while (~scanf("%d%d%d", &n, &m, &k)) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
scanf("%d", &a[i][j]);
sort(a[i], a[i] + m, compare);
}

    len = m;
    for (int i = 1; i < n; i++)
        merge(a[0], a[i], a[0]);

    // for(int i = 0;i < max(m,k); i++)
    //     printf("%d ",a[0][i]);
    // printf("\n");

    printf("%d\n", a[0][k - 1]);
}

return 0;

}

{% endfold %}