当前位置: 代码迷 >> 综合 >> poj 2442 Sequence 优先队列的运用
  详细解决方案

poj 2442 Sequence 优先队列的运用

热度:12   发布时间:2024-01-19 06:03:38.0

题意:

给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;	
} 


  相关解决方案