撰写- 总时间限制:
- 6000ms
- 内存限制:
- 65536kB
- 描述
- 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?
- 输入
- 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.
- 输出
- For each test case, print a line with the smallest n sums in increasing order, which is separated by a space.
- 样例输入
-
1 2 3 1 2 3 2 2 3 - 样例输出
-
3 3 4
题意：给出M个长度为N的整数序列，从每个序列中任取一个求和，共有N^M个和，求其中最小的N个和，N<=2000,M<=100
题解：
- 先考虑M=2的情况，当M=2时，先将A[]与B[]进行从小到大排序，那么最小值就是A[1]+B[1]，第二小的值为min( A[1+1]+B[1], A[1]+B[1+1]，显然当我们确定了第k小的值的时候，第k+1小的值就是A[i+1]+B[j]与A[i]+B[j+1]其中之一。
- 但是这样的枚举可能会重复，所以我们规定：如果把j加1产生新的备选方案，那么以后只能再加j，不能再加i。类似于dp，这样已经遍历了所有可能的方案。
- 算法步骤：建立一个小根堆，里面存储node(i,j,last)三元组，以A[i]+B[j]的值作为比较的节点权值。
- 向堆中插入（1，1，false）
- 取出堆顶的(i,j,last),向堆中插入(i,j+1,true),如果last==false，那么向堆中插入(i+1,j,false);
- 步骤2进行n次
- 数学归纳法，先求出前两个序列的前N小和，再将第三个序列与得出的前两个序列的前N小和求前N小和，最终得到M个序列任取一个数相加构成的前N小和。
- 时间复杂度O(MNlog(N)).
//#include<bits/stdc++.h>
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
return b ? gcd(b, a%b) : a;
}
template <class T>
inline bool scan_d(T &ret) {
char c;
int sgn;
if(c=getchar(),c==EOF) return 0; //EOF
while(c!='?'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='?')?-1:1;
ret=(c=='?')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
ret*=sgn;
return 1;
}
inline void outt(int x) {
if(x>9) outt(x/10);
putchar(x%10+'0');
}
const int MAXN = 1e6+10;
int n,t,m;
int a[2010];
int b[2010];
int c[2010];
struct node{
int x;
int y;
bool last;
node(int _x=0,int _y=0,bool _last=0):x(_x),y(_y),last(_last){}
bool operator < (const node &B) const{//这里的const别丢了
return a[x]+b[y]>a[B.x]+b[B.y];
}
};
priority_queue<node>q;
int main(){
cin>>t;
while(t--){
scanf("%d%d", &n,&m);
rep(i,1,m)scanf("%d", &c[i]);
sort(c+1,c+m+1);
rep(i,2,n){
rep(j,1,m){
scanf("%d", &b[j]);
}
sort(b+1,b+m+1);
rep(j,1,m){
a[j]=c[j];
}
while(!q.empty())q.pop();
q.push(node(1,1,false));
rep(j,1,m){
node p=q.top();
c[j]=a[p.x]+b[p.y];
q.pop();
q.push(node(p.x,p.y+1,true));
if(p.last==false){
q.push(node(p.x+1,p.y,false));
}
}
}
rep(i,1,m){
printf("%d ", c[i]);
}
cout<<endl;
}
return 0;
}