AcWing 146. 序列
宋标 Lv5
  2022-08-18 02:31:33 2022-08-18 02:31    

题目

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

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

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

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

输入格式

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

接下来输入 组测试用例。

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

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

输出格式

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

每组输出占一行。

数据范围

,

输入样例：

1
2 3
1 2 3
2 2 3

输出样例：

3 3 4

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 2010;

int m, n;

int a[N], b[N], c[N];

void q_sort(int a[], int l, int r)
{
    if (l >= r) return;
    int i = l - 1, j = r + 1, t = a[l];

    while (i < j)
    {
        while (a[++ i] < t);
        while (a[-- j] > t);
        if (i < j) swap(a[i], a[j]);
    }
    q_sort(a, l, j);
    q_sort(a, j + 1, r);
}

void merge()
{
    priority_queue<PII, vector<PII>, greater<PII>> heap;

    // a数组有序, a[0]最小，与b数组组合
    for (int i = 0; i < n; ++ i) heap.push({b[i] + a[0], 0});

    // c数组存储递增最小序列和
    for (int i = 0; i < n; ++ i)
    {
        auto t = heap.top();
        heap.pop();
        int v = t.first, p = t.second;
        c[i] = v;
        heap.push({v - a[p] + a[p + 1], p + 1});
    }

    memcpy(a, c, sizeof a);
}

int main()
{
    int T;
    scanf("%d", &T);

    while (T --)
    {
        scanf("%d%d", &m, &n);

        for (int i = 0; i < n; ++ i) scanf("%d", &a[i]);

        q_sort(a, 0, n - 1);

        for (int i = 1; i < m; ++ i)
        {
            // 两两归并
            for (int j = 0; j < n; ++ j) scanf("%d", &b[j]);
            merge();
        }

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

    return 0;
}
 评论