洛谷P1090 合并果子 && STL ＜queue＞容器讲解

一、头文件

queue模板类的定义在头文件中。

二、分类

1.queue

先进先出 即先放进去的元素先出来

语法：

①queue< 数据类型>容器名（这里设为 q）；

②q.push(); //在末尾加入一个元素；

q.back( ); //返回一个引用，指向队列的最后一个元素。

q.empty(); //如果队列为空函数返回真(1)，否则返回假(0)。

q.front();//返回队列第一个元素。

q.pop();//删除队列第一个元素。

q.size() ;//返回队列中元素的个数。

//简单演示
#include<queue>
queue<int>q;
q.push(2);
q.push(3);
cout<<q.front()<<endl;
q.pop();
cout<<q.front()<<endl;
//output:
2
3
           

2.priority_queue

优先队列，默认把数值大的放在前面

语法

①priority_queue< Type >name； //默认从大到小

priority_queue< Type，vector< Type>, greater< Type> >name;//从小到大

②q.top();//返回队列第一个元素。

注：priority_queue与queue返回第一个元素的函数不同。

q.push(); //在末尾加入一个元素；

q.back( ); //返回一个引用，指向队列的最后一个元素。

q.empty(); //如果队列为空函数返回真(1)，否则返回假(0)。

q.pop();//删除队列第一个元素。

q.size() ;//返回队列中元素的个数。

//简单演示
#include<queue>
priority_queue<int>q;
q.push(2);
q.push(3);
cout<<q.top()<<endl;
q.pop();
cout<<q.top()<<endl;
//output:
3
2
//
priority_queue<int, vector<int>, greater<int> >q;
q.push(2);
q.push(3);
cout<<q.top()<<endl;
q.pop();
cout<<q.top()<<endl;
//output:
2
3

           

例题：洛谷P1090 合并果子

#include<bits/stdc++.h>
const int N=10005;
using namespace std;
int main(){
	priority_queue<int, vector<int>, greater<int> >q;
	int n;
	int a[N];
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		q.push(a[i]);
		
	}
	int ans=0;
	while(q.size()>1) {
		int a=q.top();
		q.pop();
		int b=q.top();
		q.pop();
		q.push(a+b);
		ans+=a+b;
	}
	cout<<ans;
	return 0;
}```