今天看了優(yōu)先隊(duì)列問題，順便水了兩道題，嘿嘿，好久沒寫博客了，今天晚上回來，宿舍的那臺大頭機(jī)居然破天荒的能夠連上網(wǎng)頁，總結(jié)一下今天的收獲……

下面是我看的關(guān)于優(yōu)先隊(duì)列資料：

在優(yōu)先隊(duì)列中，優(yōu)先級高的元素先出隊(duì)列。
標(biāo)準(zhǔn)庫默認(rèn)使用元素類型的<操作符來確定它們之間的優(yōu)先級關(guān)系。
優(yōu)先隊(duì)列的第一種用法，也是最常用的用法：

priority_queue<int> qi;

通過<操作符可知在整數(shù)中元素大的優(yōu)先級高。
故示例1中輸出結(jié)果為：9 6 5 3 2

第二種方法：
在示例1中，如果我們要把元素從小到大輸出怎么辦呢？
這時(shí)我們可以傳入一個(gè)比較函數(shù)，使用functional.h函數(shù)對象作為比較函數(shù)。

priority_queue<int, vector<int>, greater<int> >qi2;

其中
第二個(gè)參數(shù)為容器類型。
第二個(gè)參數(shù)為比較函數(shù)。
故示例2中輸出結(jié)果為：2 3 5 6 9

第三種方法：
自定義優(yōu)先級。

struct node { friend bool operator< (node n1, node n2) { return n1.priority < n2.priority; } int priority; int value; };

在該結(jié)構(gòu)中，value為值，priority為優(yōu)先級。
通過自定義operator<操作符來比較元素中的優(yōu)先級。
在示例3中輸出結(jié)果為：
優(yōu)先級 值
9 5
8 2
61
23
14
好吧，下面是我做的題目：

題目：坦克大戰(zhàn)（貌似POJ上也有）

地址： 猛擊

代碼如下：

時(shí)間：0ms 內(nèi)存：660

<span style="font-size: 13px;">#include<stdio.h> #include<queue> #include<string.h> using namespace std; struct node { int x,y,step; }; struct cmp //定義優(yōu)先級 { bool operator()(node s,node t) { return s.step > t.step; } }; int map[301][301],shangxia[4]={0,0,1,-1},zuoyou[4]={1,-1,0,0}; int search(int x,int y) { int i,j,count=1; node temp={x,y,count}; priority_queue<node,vector<node>,cmp> Q; Q.push(temp); while(!Q.empty()) { Q.pop(); for(int k=0;k<4;k++) { i=x+zuoyou[k]; j=y+shangxia[k]; if(map[i][j]==4) return count; if(map[i][j]) { node r={i,j,count+map[i][j]}; Q.push(r); map[i][j]=0; } } count=Q.top().step; x=Q.top().x; y=Q.top().y; } return -1; } int main() { int x,y,i,j; char str; while(scanf("%d%d",&x,&y),x+y) { memset(map,0,sizeof(map)); for(i=1;i<=x;i++) { getchar(); for(j=1;j<=y;j++) { scanf("%c",&str); if(str=='S'||str=='R') map[i][j]=0; if(str=='E')map[i][j]=1; if(str=='B')map[i][j]=2; if(str=='Y')map[i][j]=3; if(str=='T')map[i][j]=4; } } for(i=1;i<=x;i++) for(j=1;j<=y;j++) if(map[i][j]==3) { printf("%d\n",search(i,j)); break; } } return 0; }</span>

題目：懶省事的小明

地址： 請猛擊

代碼如下：

時(shí)間: 116ms 內(nèi)存：308

#include<stdio.h> #include<functional> //greater函數(shù)頭文件 #include<queue> using namespace std; int main() { int ncase,n,i,temp,a,b,sum; priority_queue<int,vector<int>,greater<int> >Q; //greater函數(shù)為比較函數(shù)見上面參考資料 scanf("%d",&ncase); while(ncase--) { sum=0; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&temp); Q.push(temp); } while(Q.size()!=1) { a=Q.top(); Q.pop(); b=Q.top(); Q.pop(); temp=a+b; Q.push(temp); sum+=temp; } Q.pop(); printf("%d\n",sum); } return 0; }

好吧，知道近些天的積累，我才知道，不以AC為目的的做題，都是扯淡，好吧，以后要多多AC，多多，學(xué)習(xí)新知識，嘿嘿……

NYOJ坦克大戰(zhàn)+懶省事的小明（優(yōu)先隊(duì)列問題）