AcWing-146-序列

2021-04-22 · 122次阅读 · 原创 · 数据结构与算法

#算法竞赛 #题解 #二叉堆

问题

给定 m 个序列，每个包含 n 个非负整数。

现在我们可以从每个序列中选择一个数字以形成具有 m 个整数的序列。

很明显，我们一共可以得到 $n^m$ 个这种序列，然后我们可以计算每个序列中的数字之和，并得到 $n^m$ 个值。

现在请你求出这些序列和之中最小的 n 个值。

输入格式

第一行输入一个整数 T，代表输入中包含测试用例的数量。

接下来输入 T 组测试用例。

对于每组测试用例，第一行输入两个整数 m 和 n。

接下在 m 行输入 m 个整数序列，数列中的整数均不超过 1000010000。

输出格式

对于每组测试用例，均以递增顺序输出最小的 n 个序列和，数值之间用空格隔开。

每组输出占一行。

数据范围

0<m≤1000,
0<n≤2000

输入样例：

输出样例：

3 3 4

思路

首先，将第一个序列排好序形成 a，接下来，每读入一个序列 b，就将其与 a 进行一次合并计算。

合并计算的分析如下：

先将 b[i] 与 a[1] 相加存入优先队列，并记录当前 a 序列下标 1 ，接下来进行 n 次出队操作，每次出队，出队元素即为第几个最小的数，同时，因为当前出队元素最小，则其对应的右边一列元素应该是下一列中的最小值，依次类推即可得出答案。

每一行从左到右递增
b[1] + a[1]	b[1] + a[2]	…	b[1] + a[n]
b[2] + a[1]	b[2] + a[2]	…	b[2] + a[n]
b[3] + a[1]	b[3] + a[2]	…	b[3] + a[n]
…	…	…	…
b[n] + a[1]	b[n] + a[2]	…	b[n] + a[n]

题解

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;
typedef pair<int, int> PII;
const int N = 2e4 + 5;
int t, m, n, a[N], b[N], c[N];

void merge() {
    priority_queue<PII, vector<PII>, greater<PII>> q;
    for (int i = 1; i <= n; i++) q.push({a[1] + b[i], 1});

    for (int i = 1; i <= n; i++) {
        auto t = q.top();
        q.pop();
        int s = t.first, p = t.second;
        c[i] = s;
        q.push({s - a[p] + a[p + 1], p + 1});
    }

    for (int i = 1; i <= n; i++) a[i] = c[i];

}

int main() {
    cin >> t;
    while (t--) {
        scanf("%d%d", &m, &n);

        for (int j = 1; j <= n; j++) scanf("%d", &a[j]);
        sort(a + 1, a + n + 1);
        for (int i = 2; i <= m; i++) {
            for (int j = 1; j <= n; j++) scanf("%d", &b[j]);
            merge();
        }

        for (int i = 1; i <= n; i++) printf("%d ", a[i]);
        puts("");
    }

    return 0;
}

标题：	AcWing-146-序列
链接：	https://www.fightingok.cn/detail/83
更新：	2022-09-18 22:37:30
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可