P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G 贪心 二叉堆 优先队列

题目：

思路：
主要是通过这道题目学习一下二叉堆和优先队列
用priority_queue来实现二叉堆（大顶堆和小顶堆）
注意要加头文件 #include <queue>
默认为大顶堆 priority_queue<int> q 小顶堆 priority_queue<数据类型,vector<数据类型>,greater<数据类型>> q
eg:

priority_queue<int,vector<int>,greater<int>> q

typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii>> q
q.top().first
q.top().second

数据类型的位置也可以放自定义的struct(struct里可以运算符重载
AC代码：
直接调用：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#define maxn 11111
using namespace std;
int n,x;
priority_queue<int,vector<int>,greater<int>> q;
long long ans;
int main()
{
    cin>>n;ans=0;for(int i=1;i<=n;i++){
    cin>>x;q.push(x);} for(int i=1;i<n;i++){
    int temp=0;temp+=q.top();//cout<<"temp1 "<<temp<<endl;q.pop();temp+=q.top();q.pop();//cout<<"temp2 "<<temp<<endl;q.push(temp);ans+=temp;//cout<<"!!!"<<ans<<endl;}cout<<ans<<endl;return 0;
}

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#define maxn 22222
using namespace std;
int n,x;
//priority_queue<int,vector<int>,greater<int>> q;
struct PQ 
{
    int a[maxn],sz=0;int size(){
    return sz;}bool empty(){
    return sz==0;}void push(int x){
    a[++sz]=x;int now=sz;while (now!=1){
    if (a[now>>1]>a[now]){
    swap(a[now>>1],a[now]);now>>=1;}else break;}}int top(){
    return a[1];}void pop(){
    a[1]=a[sz--];int now=1;while (now<<1<=sz){
    if (a[now<<1]<a[now]&&a[now<<1|1]<a[now]){
    if (a[now<<1]<a[now<<1|1]) {
    swap(a[now<<1],a[now]);now=now<<1;}else {
    swap(a[now<<1|1],a[now]);now=now<<1|1;}}else{
    if (a[now<<1]<a[now]) {
    swap(a[now<<1],a[now]);now=now<<1;}else if (now<<1<sz&&a[now<<1|1]<a[now]) {
    swap(a[now<<1|1],a[now]);now=now<<1|1;}else break;}}}
}q;
long long ans;
int main()
{
    cin>>n;ans=0;for(int i=1;i<=n;i++){
    cin>>x;q.push(x);} for(int i=1;i<n;i++){
    int temp=0;temp+=q.top();//cout<<"temp1 "<<temp<<endl;q.pop();temp+=q.top();q.pop();//cout<<"temp2 "<<temp<<endl;q.push(temp);ans+=temp;//cout<<"!!!"<<ans<<endl;}cout<<ans<<endl;return 0;
}