POJ2442Sequence

http://poj.org/problem?id=2442

题意 ：就是输入m个数集，每个含n个数，求从每个集合取一个数后，按非降序输出前n小的和。

思路 ： 本来打算是用几个for循环的，后来觉得要是真这么简单就不会在堆里分类了，所以，经过会神详细指导讲解，略懂略懂，弄俩优先队列，正好搞定

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<vector>

 #include<iostream>

 using namespace std ;

 const int maxn =  ;

 int main()

 {

     int n ;

     scanf("%d",&n);

     int m,t,s;

     int a[maxn] ;

     for(int i =  ; i <= n ; i++)

     {

         priority_queue<int ,vector<int>,less<int> > Q;//大根堆是用来找和最小的值的

         priority_queue<int ,vector<int>,greater<int> > P;//小根堆是将输入的每行数从小到大排序

         scanf("%d %d",&m,&t);

         for(int h =  ; h < t ; h++)

         {

             scanf("%d",&s);//先输入第一行

             P.push(s);

         }

         for(int h =  ; h < m ; h++)

         {

             for(int j =  ; j < t ; j++)

                 scanf("%d",&a[j]) ;

             while(!P.empty())

             {

                 int b = P.top();

                 P.pop();

                 for(int j =  ; j < t ; j++)

                 {

                     if(Q.size() == t && b+a[j] < Q.top())

                     {

                         //如果大根堆里已经有了t个数了，那就判断首元素与b+a[j]谁大，若是大，就删掉，加入新的

                         Q.pop();

                         Q.push(b+a[j]);

                     }

                     else if(Q.size() < t)

                         Q.push(b+a[j]) ;

                 }

             }

             while(!Q.empty())

             {

                 P.push(Q.top());

                 Q.pop();

             }

         }

         printf("%d",P.top()) ;

         P.pop();

         for(int k =  ; k < t ; k++)

         {

             printf(" %d",P.top()) ;

             P.pop();

         }

         printf("\n");

         //memset(sh,0,sizeof(sh));

     }

     return  ;

 }