ブルーブリッジカップ基礎入門——STLのstack、queue、priority_queue

ブルーブリッジ杯入門——STLのstack、queue、priority_queue
「データ構造」という授業では、スタック、キュー、スタック(STLではスタックを優先キューpriority_queueと命名)などの構造を学び、まだこの授業を習っていない学生もいるかもしれませんが、大丈夫です.基本的な概念を理解して、2回多く使うと、試合でどのようにこれらの構造を使うかがわかります.次に、試合で理解しなければならないスタック、スタック、キューの知識を見てみましょう.

stack(スタック)(1)簡介スタックは、後進先出原則に従ってデータを格納するデータ構造であり、データの読み取りはスタックの上部で行われ、下部は動かない.挿入削除を行う一端をスタックトップと呼び,他端をスタックベースと呼び,挿入操作をスタックインと呼び,削除操作をスタックバックと呼ぶ.私たちはスタックをエレベーターと見なすことができて、エレベーターに乗る人はスタックの記憶のデータと見なすことができて、先進的なエレベーターの人はいつも中に閉じ込められて、後ろに入った人が出てから出ることができて、後ろに入った人は、いつも先に出て行きます.(2)ヘッダファイル

#include

(3)定義

//stack   
stack<int>s1;
stack<string>s2;

(4)基本操作

stack<int>s;//   
s.push(x);//  ，   x   
s.pop();//  ，       ，      
s.top();//      
s.empty();//          ，     true
s.size();//        

queue(キュー)(1)概要キューは、先進的な先出し原則に従ってデータを格納するデータ構造であり、テーブルの先端でのみ削除操作を許可し、テーブルの後端で挿入操作を行い、スタックと同様に、キューは操作が制限された線形テーブルである.挿入操作を行う端がキューの最後となり,削除操作を行う端をキューと呼ぶ.列は、私たちが食堂の窓口で列に並んで料理をするときの列のように、列に並んでいる学生は列に格納されているデータ要素であり、新しく来た学生は列のしっぽから列に挿入するしかなく、料理を打って離れた学生は、必ず列の一番前の同学であり、列の先頭から離れるしかない.(2)ヘッダファイル

#include

(3)定義

//queue   
queue<int>q1;
queue<string>q2;

(4)基本操作

queue<int>q;//   
q.push(x);//  ，   x       
q.pop();//  ，          ，  ，            
q.front();//      ，             
q.back();//      ,             
q.empty();//        
q.size();//          

priority_Queue(プライオリティキュー)(1)プロフィールプライオリティキューは、エンキュー順ではなく、キュー内の要素のプライオリティ順でデキューされます(デフォルトでは、プライオリティが大きいデータが先にデキューされますが、演算子を指定することで独自の優先順位を指定することもできます).優先キューを定義するには、3つのパラメータ、データ型、コンテナタイプ、および比較演算子(sort関数の比較関数cmpに似た役割を果たす)があります.このうち後ろの2つは省略できます.(2)ヘッダファイル

#include

(3)定義

//priority_queue   
priority_queue<int>q1;
priority_queue< pair<int,int> >q2;//             
priority_queue<int,vector<int>,greater<int> >q3;//        ，       x>y
priority_queue<int,vector<int>,less<int> >q3;//        ，       x

(4)基本操作

priority_queue<int>q;//      
q.push(x);// x   
q.pop();//      
q.top();//          
q.empty();//      （ ）    
q.size();//      （ ）      

(5)例題優先キューは強力なデータ構造であり、キューの動的秩序性を維持し、エンキュー操作を絶えず変更し、最大または最小値を求める問題を解決するのに適している.次に、実際の問題の解決における優先キューの応用を例として説明する.「south_を参照」windのブログ【問題説明】ある果樹園では、すでにすべての果物を打ち落とし、果物の種類によって異なる山に分けていることが多い.すべての果物をたくさん合成することにした.合併するたびに、多くの場合、2つの果物を統合することができ、消費された体力は2つの果物の重量の和に等しい.すべての果物はn-1回の合併を経て、1山しか残っていないことがわかる.果物を合併するときに消費される体力の多くは、合併するたびに消費される体力の和に等しい.これらの果物を家に運ぶのに力を入れなければならないので、果物を合併するときはできるだけ体力を節約しなければならないことが多い.各果物の重量が1であり、既知の果物の種類数と各果物の数を仮定すると、あなたの任務は合併の順序案を設計し、多くの体力を最小限に抑え、この最小の体力消費値を出力することです.例えば3種類の果物があり、数は1,2,9の順である.まず1、2スタックを統合することができ、新しいスタックの数は3で、体力を消費するのは3です.次に、新しいスタックを元の第3のスタックと統合し、新しいスタックを得、数は12であり、体力は12である.そのため、体力=3+12=15を多く消費します.15が最小の体力消費値であることが証明される.【入力ファイル】入力ファイルfruit.inは、果物の種類数を表す整数n(1<=n<=10000)の2行を含む.2行目はn個の整数を含み、スペースで区切られ、i番目の整数ai(1<=ai<=20000)はi番目の果物の数である.【出力ファイル】出力ファイルfruit.outは、1つの整数、すなわち最小の体力消費値のみを含む行を含む.入力データは、この値が231未満であることを保証する.【サンプル入力】3 1 2 9【サンプル出力】15【データ規模】30%のデータに対して、n<=1000を保証する.50%のデータに対して、n<=5000が保証されている.すべてのデータに対して、n<=10000が保証されます.
問題解:最小の2つのスタックをマージするたびに、1つのスタックしか残っていません.詳細コードは次のとおりです.

#include    
#include    
struct cmp  
{  
    bool operator ()(const int &i,const int &j)  
    {  
        return i>j;  
    }  
};  
using namespace std;  
int main()  
{  
    priority_queue<int,vector<int>,cmp> s;  
    int n;  
    while(cin>>n)  
    {  
        for(int i=0;i<n;i++)  
        {  
            int key;  
            scanf("%d",&key);  
            s.push(key);  
        }  
        int sum=0;  
        while(n>=2)  
        {  
            int a,b;  
            a=s.top();  
            s.pop();  
            b=s.top();  
            s.pop();  
            s.push(a+b);  
            //cout<sum+=a+b;  
n--;  
}  
cout<<sum<<endl;  
}  
return 0;  
}

優先キューの使用定義

#include
#include//     
using namespace std;
struct cmp{
  bool operator ()(const        ,       ){
       //       ， return i>j;
  }
};
struct node{
  friend bool operator<(node a,node b){
     if(   ) return   ;
     else  return    ;
  }
};
int main(){
  priority_queue<    ,vector(    ),cmp>s;//        
  priority_queue<node>que;//        
  ///    
  for(int i=0;i<n;i++)
    s.push(x)//    
  while(flag){
    a=s.top();//         
    s.top();//     
  }
  return 0;
}