Sequence
| Time Limit: 6000MS | Memory Limit: 65536K | |
| Total Submissions: 9285 | Accepted: 3097 |
Description
Given m sequences, each contains n non-negative integer. Now we may select one number from each sequence to form a sequence with m integers. It's clear that we may get n ^ m this kind of sequences. Then we can calculate the sum of numbers in each sequence, and get n ^ m values. What we need is the smallest n sums. Could you help us?
Input
The first line is an integer T, which shows the number of test cases, and then T test cases follow. The first line of each case contains two integers m, n (0 < m <= 100, 0 < n <= 2000). The following m lines indicate the m sequence respectively. No integer in the sequence is greater than 10000.
Output
For each test case, print a line with the smallest n sums in increasing order, which is separated by a space.
Sample Input
1
2 3
1 2 3
2 2 3
Sample Output
3 3 4
Source
POJ Monthly,Guang Lin
题目意思：
有m组序列，每组有n个数。从每组中取一个数并求和，输出最小的n个和。
解题思路：
输入一组处理一组，先求出前两组数的n个最小和，再输入一组数，将这组数与前面的n个最小和一起处理，再求出这两组数的n个最小和…………直到m组数全部输入处理完毕。
处理过程如下：
①第一组数输入A数组中后降序排列，第二组数输入B数组后也降序排列
②将A[0]+B[i]这n个数先入队，再依次遍历A数组剩下的n-1个数与B数组的n个数之和，每次比较将较小的和入队。
③遍历完毕后，将队列中元素赋给A数组，同时队列清空。
④输入下一组数到B数组，重复②，直到m组数输入处理完毕。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
const int MAXN=30030;
int a[MAXN],b[MAXN];
using namespace std;
int main()
{
#ifdef ONLINE_JUDGE
#else
freopen("F:/cb/read.txt","r",stdin);
//freopen("F:/cb/out.txt","w",stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while(t--)
{
priority_queue<int>q;//最大值优先
int m,n;
cin>>m>>n;
for(int i=0; i<n; ++i)
cin>>a[i];
sort(a,a+n);//升序排列
--m;
while(m--)
{
for(int i=0; i<n; ++i)
cin>>b[i];
sort(b,b+n);
for(int i=0; i<n; ++i)//入队
q.push(a[0]+b[i]);
for(int i=1; i<n; ++i)//依次比较将较小的和入队
for(int j=0; j<n; ++j)
{
int temp=a[i]+b[j];
if(temp<q.top())
{
q.pop();
q.push(temp);
}
}
for(int i=0; i<n; ++i)//将队列中的数赋给a数组，同时队列清空
{
a[i]=q.top();
q.pop();
}
sort(a,a+n);
}
for(int i=0; i<n-1; ++i)//输出结果
cout<<a[i]<<" ";
cout<<a[n-1]<<endl;
}
return 0;
}
/*
1
2 3
1 2 3
2 2 3
*/
测试数据：
2
2 3
1 2 3
2 2 3
10 10
21 12 123 3 21 123 32 143 43 56
2 32 43 34 54 56 656 76 43 234
234 45 5 65 56 76 43 23 435 57
32 324 435 46 56 76 87 78 43 23
3 32 324 45 56 57 34 23 54 565
23 32 34 342 324 232 2 432 324 12
234 324 4 45 65 67 435 23 5 654
34 3245 345 56 56 657 67 456 345 325
234 234 546 65 88 66 53 654 65 765
5 3 34 34 34 56 345 234 2 34
运行结果：
3 3 4
131 132 132 133 134 135 140 140 141 141