Luogu P1392 取数

题目描述

https://www.luogu.com.cn/problem/P1392

Solution

假设只有两组序列 $a$ 和 $b$，我们将 $a$ 和 $b$ 进行排序

那么最小的数显然是 $a_1+b_1$，第二小的数一定是 $a_2+b_1$ 或 $a_1+b_2$

我们维护一个小根堆，每次取出 $a_x+b_y$ 的时候扔进去 $a_{x+1}+b_y$ 和 $a_x+b{y+1}$

为了不进行判重，我们首先扔进去 $a_1+b_i,i\in[1,m]$，然后每次取出 $a_x+b_y$，扔进去 $a_{x+1}+b_y$

现在有多组序列，我们每次两两合并即可

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#define maxn 810
#define ll long long
#define cQ const Queue
using namespace std;

int n, m, k, a[maxn], b[maxn], c[maxn];

struct Queue {
    int x, y;

    Queue() {}
    Queue(int _x, int _y) { x = _x; y = _y; }

    friend bool operator < (cQ &u, cQ &v) { return a[u.x] + b[u.y] > a[v.x] + b[v.y]; } 
} ; priority_queue<Queue> Q;

int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= m; ++i) cin >> a[i];
    sort(a + 1, a + m + 1); 
    for (int o = 2; o <= n; ++o) {
        for (int i = 1; i <= m; ++i) cin >> b[i];
        sort(b + 1, b + m + 1); while (!Q.empty()) Q.pop();
        for (int i = 1; i <= m; ++i) Q.push(Queue(1, i));
        for (int i = 1; i <= k; ++i) {
            Queue u = Q.top(); Q.pop();
            c[i] = a[u.x] + b[u.y]; Q.push(Queue(u.x + 1, u.y));
        }
        for (int i = 1; i <= k; ++i) a[i] = c[i]; 
    }
    for (int i = 1; i <= k; ++i) cout << a[i] << " "; puts("");
    return 0;
}