题目题解：

有关博客： 优先队列不错的博客。

 

priority_queue 对于基本类型的使用方法相对简单。

他的模板声明带有三个参数，priority_queue<Type, Container, Functional>

Type 为数据类型， Container 为保存数据的容器，Functional 为元素比较方式。

Container 必须是用数组实现的容器，比如 vector, deque 但不能用 list.

STL里面默认用的是 vector. 比较方式默认用 operator< ,

 

 所以如果你把后面俩个

参数 缺省的话，优先队列就是大顶堆，队头元素最大。

 

 

 

如果要用到小顶堆，则一般要把模板的三个参数都带进去。

STL里面定义了一个仿函数 greater<>，对于基本类型可以用这个仿函数声明小顶堆

例子:

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #define LL long long 7 using namespace std; 8  9 struct node10 {11     int x, y;12     bool operator < (const node &tmp)const13     {14         return x > tmp.x;15     }16 };17 int main()18 {19     priority_queue
          
           q1; //基本类型从大到小20 priority_queue
           

, greater

>q2; //基本类型从小到大21 priority_queue

q3; //自定义类型22 return 0;23 }

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;int main(){ int n,a,sum,sum1; long long int count; priority_queue
             

, greater

>q; while(scanf("%d",&n)!=EOF) { count=0; for(int i=1; i<=n; i++) { scanf("%d",&a); q.push(a); } if(n==1) { printf("%d\n",count); continue; } else { while(!q.empty()) { sum=q.top(); q.pop(); if(q.empty()) { break; } sum1=q.top(); q.pop(); q.push(sum+sum1); count=count+sum+sum1; } printf("%d\n",count); } } return 0;}