(这排版我真搞不懂,明明我这边是OK的)
题目大意:
给定 m 个序列
每个包含 n个非负整数。
现在我们可以从每个序列中选择一个数字以形成具有 m个整数的序列。
很明显,我们一共可以得到 n^m 个这种序列,然后我们可以计算每个序列中的数字之和,并得到 n^ m 个值。
现在请你求出这些序列和之中最小的 n个值。
题解:
假设现在只有两个序列,a1 a2 a3 a4... an,b1 b2 b3 b4...bn,从每一个序列中取出一个数求和一共有n*n种。
现在想把这n*n种结果分成n组。
首先把a[]排序,使它单调递增,b[]是否有序无所谓。
b1+a1, b1+a2,b1+a3,b1+a4....b1+an (第一组)
b2+a1,b2+a2,b2+a3,b2+a4...b2+an(第二组)
b3+a1,b3+a2,b3+a3,b3+a4...b3+an(第三组)
....
bn+a1,bn+a2,bn+a3,bn+a4...bn+an(第n组)
可以看出,由于a[]是单调递增的,所以每一组的元素也是单调递增的。
那么n*n种结果中最小的n个,肯定是所有组中的第一个。
将最小的那个删去,然后被删结果所在组下一个数加入最小n个数中去。(优先队列实现)
#include<iostream> #include<cstdio> #include<queue> #include<cstring> #include<algorithm> using namespace std; const int N=2002; typedef pair<int,int> PII; int T; int m,n; int a[N],b[N],c[N]; /* b1+a1 b1+a2 b1+a3 b1+a4 b1+a5 */ void merge() { priority_queue<PII,vector<PII>,greater<PII>>heap; for(int i=1;i<=n;i++) heap.push({b[i]+a[1],1}); for(int i=1;i<=n;i++) { PII tmp=heap.top(); heap.pop(); c[i]=tmp.first; int id=tmp.second; heap.push({c[i]-a[id]+a[id+1],id+1}); } for(int i=1;i<=n;i++) a[i]=c[i]; } int main() { scanf("%d",&T); while(T--) { // cout<<"yes"; scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); for(int i=1;i<m;i++) { for(int j=1;j<=n;j++) { scanf("%d",&b[j]); } merge(); } for(int i=1;i<=n;i++) printf("%d ",a[i]); printf("\n"); } return 0; }