题意:
给m行,每行n个数,从每行取一个数计算和,求前n小的和。
分析:
优先队列的运用,主要是make_heap,pop_heap,push_heap三个STL函数的用法。
代码:
//poj 2442
//sep9
#include <iostream>
#include <algorithm>
using namespace std;
const int maxN=2048;
int a[maxN],b[maxN],sum[maxN];int main()
{int cases;scanf("%d",&cases);while(cases--){int i,j,k,m,n;scanf("%d%d",&m,&n);for(i=0;i<n;++i)scanf("%d",&a[i]);for(i=1;i<m;++i){sort(a,a+n);for(j=0;j<n;++j)scanf("%d",&b[j]);sort(b,b+n);for(j=0;j<n;++j)sum[j]=a[j]+b[0];make_heap(sum,sum+n);for(j=1;j<n;++j){for(k=0;k<n;++k){int x=b[j]+a[k];if(x>=sum[0])break;pop_heap(sum,sum+n);sum[n-1]=x;push_heap(sum,sum+n);}}memcpy(a,sum,n*sizeof(a[0])); }sort(a,a+n); for(i=0;i<n;++i)printf("%d ",a[i]);printf("\n");}return 0;
}