[ACM]POJ 2442 Sequence(ヒープの性質)

14743 ワード

データ構造 ACM 積み重ねる

Sequence
Time Limit:600 MS

メモリLimit:65536 K
Total Submissions:7011

Acceepted:2262
Description
Given m sequence s,each contains n non-negative integer.Now we may select one number from each sequence to form a sequence with m integer s.It's clear thaaaaaaaawe may gen^m thisiskikikid of sequences.The e e e e e e e thethethethethetherererererererererererererererererecececencncncnce e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e m s.Could you help us?
Input
The first line is an integer T,which shows the number of test cases,and the n T test cases follows.The first line of each case two integers m,n(0<=100,n==2000).The follatwint therectiness.
Output
For each test case,print a line with the smalest n sums in increase order,which is separated by a space.
Sample Input

Sample Output

3 3 4

ソurce
POJ Monthly、Gung Lin
問題解決の考え方:
m行があって、行ごとにn個の数を取り出して一つの数を足し合わせてsumを求めます.このようなsumはnのm乗個があります.要求された最初のn個の最小のsum値.
STLの中のヒープは初めて使います.最初はポップにします.heap()はちょっと分かりませんが、配列heap[n]に対しては最大でn-1ビルドと表記されています.デフォルトでは大屋根ヒープが作られています.heap[0]は配列の中で最大の数です.heap()文は、heap[0]とheap[n-1]を交換し、heap[0]からheap[n-2](最後の要素を除く)に再度ヒープを再構築し、heap[0]は依然として最大値であり、これは最大値を更新する操作に相当する.
この問題に対して、山の性質はとても良い運用ができます.3つの配列old[n],new[n],heap[n],old[]は、前のi行の要素を1行ごとに取り出して得た最初のn個の最小sum,new[n]はi＋1行目の入力要素であり、heap[n]は中間配列であり、その最大値元素を更新し、処理が完了するごとに、前のi行のap[hen]を取得する.元素はold[]に賦与して、このように前のm行は全部処理し終わった後に、更にold[]配列に対して小さい時から大きい順に並べば、出力は求められました.
以下は具体的にheap[]の役割を説明します.
最初に1行目の要素をold[]に与えて並べ替えて、1行目の要素を2行目の並べ替え後の最初の要素に加えて、n個の値をheap[]に入れて、仮の2行前のn個のsum値を得ましたが、これは必ずしも前の2行の最小の最初のn個のsum値ではありません. ,二行目にもn個の要素がありますので、全ての場合(つまり二行目の二番目、三番目…元素はそれぞれ第一行の全ての値に加算してsum値を獲得します)を挙げて、これらの全ての場合の中で一番小さいn個を取って、山の役割を果たします.前に述べた臨時のn個のsum値はheap[]の中に保存しました.heap(heap、heap+n)デフォルトの大一番上の山、つまりheap[0]は最大値です.列挙する時、求められた一時的なsum値(temp)がheap[0]より小さいと発見されたら、heap[0]の更新が必要です.前のn個の最小のsum値を要求します. 最大値heap[0]とheap[n-1]を交換して、他のheap[n-1]=tempを追加します.これでheap[]の最大値が更新されましたが、配列のどの値なのかは分かりません.pusshuheap(heap+heap); ヒープを再構築することに対して、このようにheapの中の最大のものはheap[0]です.列挙が終わったら、更新が終わったら、前の二行のn個の最小のsum値を求めます.残りの行は同じ操作です.上の並べ替えは不必要な操作を減らすために、列挙の時に早めに退出できます.これは並べ替えの2、4、5、6と最小の値を必要とします.2を取って、後の数を考慮しなくてもいいです.
コード:

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=2010;
int Old[maxn],New[maxn],heap[maxn];

int main()
{
    int t;cin>>t;
    int m,n;
    while(t--)
    {
        cin>>m>>n;
        for(int i=0;i<n;i++)
            cin>>Old[i];
        sort(Old,Old+n);
        m--;
        while(m--)
        {
            for(int i=0;i<n;i++)
                cin>>New[i];
            sort(New,New+n);
            for(int i=0;i<n;i++)
                heap[i]=Old[i]+New[0];
            make_heap(heap,heap+n);//     ，heap[0]     

            //     heap        ，            
            for(int i=1;i<n;i++)//        
            {
                bool ok=0;
                for(int j=0;j<n;j++)//   
                {
                    int temp=New[i]+Old[j];
                    if(temp<heap[0])
                    {
                        pop_heap(heap,heap+n);//heap                 （   ）  ，                  
                        heap[n-1]=temp;
                        push_heap(heap,heap+n);
                        ok=1;//       
                    }
                    else //      j         i               ，           ，          ，     heap       
                        break;
                }
                if(!ok)//       i         n         heap[]      ，   i+1         ，     
                    break;
            }
            for(int i=0;i<n;i++)
                Old[i]=heap[i];
            sort(Old,Old+n);
        }
        for(int i=0;i<n-1;i++)
            cout<<Old[i]<<" ";
        cout<<Old[n-1]<<endl;
    }
    return 0;
}

下に山の知識を貼ってください.http://blog.csdn.net/hnust_xiehonghao/article/details/9172875転載する
最大ヒープ最小スタックコードの実現
http://blog.csdn.net/xiaoxiaoxuewen/article/details/7570621
最大山の最小積原理図
http://www.cnblogs.com/wu8685/archive/2010/12/30/1922218.html
STLのスタック操作
http://hi.baidu.com/solofancy/item/14acd02b9743f7d30f37f927
http://blog.csdn.net/morewindows/article/details/6967409
STLのスタック操作上のブログから
STLの中の山の操作は4つしか使われていません.makeuheap()、popuheap()、pshuheap()、sortuheap(); 彼らの頭のファイルの関数は〹includeです.
まずはmake apです. 彼の関数の原型はvoid makeuheapです. 一つのパラメータは配列またはベクトルの頭ポインタで、二つ目のベクトルは尾ポインタです.三つ目のパラメータは比較関数の名前です.デフォルトでは大和スタックです. 作用:この区間の配列またはベクトルを一つの山の構造にします.範囲は(first、last)です. そしてポピュアですその関数の原型はvoid popuheapです. 作用:popuheapは本当に最大の要素を山から着弾させるのではなく、再び積み上げます. firstとlastを交換して、[first、last-1]のデータをもう一つの山に作ります. 続いてpusshap()void pusshheap(first upload nter、endypupload、comprefunction)です. 役割:pusshuheap()は「first、last-1」が有効な山だと仮定して、その中の新しい元素を加えて、山を作っていきます. 最後はsortuheapです.void sortuheapです.
作用は、sortuheapが「first,last」のシーケンスを並べ替えるものです.このシーケンスが有効な山だと仮定します. ,並べ替えをしたら効果的な山ではないです.
例:

#include<algorithm>
#include<cstdio>
using namespace std;
bool cmp(int a,int b)
{
  return a>b;
}
int main()
{
  int i,number[20]={29,23,20,22,17,15,26,51,19,12,35,40};	
  make_heap(&number[0],&number[12]);	
  //   :51 35 40 23 29 20 26 22 19 12 17 15	
  for(i=0;i<12;i++)		
    printf("%d ",number[i]);
  printf("
");	
  make_heap(&number[0],&number[12],cmp);
  //  ：12 17 15 19 23 20 26 51 22 29 35 40
  for(i=0;i<12;i++)		
    printf("%d ",number[i]);	
  printf("
");	
  //    8	
  number[12]=8;	
  //     	
  push_heap(&number[0],&number[13],cmp);	
  //  ：8 17 12 19 23 15 26 51 22 35 40 20	
  for(i=0;i<13;i++)		
    printf("%d ",number[i]);	
  printf("
");	
  //    8	
  pop_heap(&number[0],&number[13],cmp);	
  //  ：12 17 15 19 23 20 26 51 22 29 35 40	
  for(i=0;i<13;i++)		
    printf("%d ",number[i]);	
  printf("
");	
  sort_heap(&number[0],&number[12],cmp);	
  //             ！	
  for(i=0;i<12;i++)		
    printf("%d ",number[i]);	
  return 0;	
}

31.Next Permutation