AOJ 912.蕊蕊的后宫团

129


题目



点击显/隐题目

蕊蕊有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




题解



直接看的话很容易想到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)) 是一个可以接受的复杂度


代码


点击显/隐代码
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
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<node> 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;
}
发布评论
  • 点击查看/关闭被识别为广告的评论