A40948. Sequence
填空题
困难
知识点
题目描述
Sequence
题目描述
给定m个数字序列，每个序列包含n个非负整数。我们从每一个序列中选取一个数字组成一个新的序列，显然一共可以构造出n^m个新序列。接下来我们对每一个新的序列中的数字进行求和，一共会得到n ^m个和，请找出最小的n个和
输入
输入的第一行是一个整数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
参考答案
#include<iostream>
#include<queue>
#include<algorithm>
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;
}
上一题
下一题