题目

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

题解

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

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

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

但是,对于前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 %}