简答题
偏难
#7481
Sequence(2023.12) 给定m个数字序列,每个序列包含n个非负整数。我们从每一个序列中选取一个数字组成一个新的序列,显然一共可以构造出n^m个新序列…
Sequence(2023.12)
给定m个数字序列,每个序列包含n个非负整数。我们从每一个序列中选取一个数字组成一个新的序列,显然一共可以构造出n^m个新序列。接下来我们对每一个新的序列中的数字进行求和,一共会得到n^m个和,请找出最小的n个和
时间限制:3000
内存限制:65536
输入
输入的第一行是一个整数T,表示测试用例的数量,接下来是T个测试用例的输入 每个测试用例输入的第一行是两个正整数m(0 < m <= 100)和n(0 < n <= 2000),然后有m行,每行有n个数,数字之间用空格分开,表示这m个序列 序列中的数字不会大于10000
输出
对每组测试用例,输出一行用空格隔开的数,表示最小的n个和
样例输入
1 2 3 1 2 3 2 2 3
样例输出
3 3 4
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">// 参考答案1
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
priority_queue<int> que;
int a[2005];
int b[2005]; // 用作中间数组
int main() {
int T;
cin >> T;
int m, n;
while (T--) {
cin >> m >> n;
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
sort(a, a + n); // 用a做总的和数组
for (int i = 1; i < m; i++) // 轮接下来的序列
{
for (int j = 0; j < n; j++) {
scanf("%d", &b[j]);
que.push(a[0] + b[j]);
}
for (int j = 1; j < n; j++) {
for (int k = 0; k < n; k++) {
if (a[j] + b[k] < que.top()) {
que.pop();
que.push(a[j] +
b[k]); // 比最大值小就顶了它,想要得到ab两个里面最小的n个数
}
}
}
for (int i = 0; i < n; i++) {
a[n - i - 1] = que.top(); // 由于是最大值堆,要反过来让a有序
que.pop(); // 队列已经被清空了,轮下一次
}
}
for (int i = 0; i < n - 1; i++)
printf("%d ", a[i]);
printf("%d\n", a[n - 1]);
}
return 0;
}</pre><pre class="brush:cpp;toolbar:false">// 参考答案2
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int m, n;
vector<int> a[105];
struct Plan {
pii ptr;
bool last; // 记录本方案是否是由ptr2++得到的
int sum;
Plan() {}
Plan(int i, int j, pii _ptr, bool _last) {
ptr = _ptr;
last = _last;
sum = a[i][ptr.first] + a[j][ptr.second];
}
bool operator<(const Plan &oth) const { return sum > oth.sum; }
} init;
priority_queue<Plan> Q;
int main() {
int T;
cin >> T;
while (T--) {
scanf("%d%d", &m, &n);
for (int i = 1; i <= m; i++) {
a[i].clear();
for (int j = 1, x; j <= n; j++) {
scanf("%d", &x);
a[i].push_back(x);
}
sort(a[i].begin(), a[i].end());
}
int i = 1;
for (int j = 2; j <= m; j++, i ^= 1) {
init = Plan(i, j, make_pair(0, 0), 0);
while (!Q.empty())
Q.pop();
Q.push(init);
a[i ^ 1].clear();
while (!Q.empty()) {
Plan now = Q.top();
Q.pop();
a[i ^ 1].push_back(now.sum);
if (a[i ^ 1].size() >= n)
break;
if (!now.last && now.ptr.first < n - 1)
Q.push(Plan(i, j, make_pair(now.ptr.first + 1, now.ptr.second), 0));
if (now.ptr.second < n - 1)
Q.push(Plan(i, j, make_pair(now.ptr.first, now.ptr.second + 1), 1));
}
}
for (int k = 0; k < a[i].size(); k++)
printf("%d ", a[i][k]);
printf("\n");
}
}</pre>
这道题暂未补解析。