C++优先队列相关知识

C++中的优先队列（Priority Queue）是一种特殊的队列，其中的元素按照一定的优先级进行排序。优先队列的特点是每次取出的元素都是优先级最高的元素。

在C++中，优先队列是通过<queue>头文件中的priority_queue模板类来实现的。下面是一个简单的示例，演示了如何使用优先队列：

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;

    // 插入元素
    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);

    // 访问队列中的元素
    std::cout << "队列中的元素: ";
    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    std::cout << std::endl;

    return 0;
}

在上述示例中，我们首先创建了一个整数类型的优先队列 pq。然后，我们使用push()函数向队列中插入元素。注意，插入的元素会根据默认的比较函数（通常是大顶堆）进行排序。

接下来，我们使用top()函数访问队列中的元素，该函数返回队列中优先级最高的元素。然后，我们使用pop()函数将队列中的元素移除，以便访问下一个优先级最高的元素。我们可以使用empty()函数检查队列是否为空。

最后，我们输出队列中的元素，可以看到它们按照优先级从高到低的顺序进行了排序。

需要注意的是，优先队列默认使用<运算符进行元素的比较，因此对于自定义类型的元素，需要重载<运算符或提供自定义的比较函数来定义元素的优先级。

优先队列在许多算法和数据结构中都有广泛的应用，例如Dijkstra算法、堆排序等。它提供了一种方便的方式来处理具有优先级的元素。

优先队列的出队顺序默认按元素值从大到小进行

例题

1、加油站

分析：因为只需要得到加几次油，并不用找到在哪个加油站加油。当油量不够时，优先在油量大的加油站加油。

#include<bits/stdc++.h>
using namespace std;
const int maxN=10005;
int A[maxN],B[maxN];
int N,L,P;

void solve()
{
	A[N]=L;
	B[N]=0;//为了方便将终点也视为一个加油站
	N++;
	priority_queue<int>que;
	int ans=0,pos=0,tank=P;//加油次数、现在的位置、油箱中的汽油量 
	for(int i=0;i<N;i++)
	{
		int d=A[i]-pos;
		while(tank<d)//油箱中的油不够时
		{
			if(que.empty())
			{
				printf("-1\n");//没油可加
				return;
			}
			tank+=que.top();//加上最大的油
			que.pop();
			ans++;
		}
		tank-=d;
		pos=A[i];//更新所在位置
		que.push(B[i]);//将该加油站的油入队
	}
	printf("%d\n",ans);
}
int main()
{
	while(scanf("%d%d%d",&N,&L,&P)&&N)
	{
		for(int i=0;i<N;i++)
		{
			scanf("%d",&A[i]);
		}
		for(int i=0;i<N;i++)
		{
			scanf("%d",&B[i]);
		}
		solve();
	}
	return 0;
}

2、修栅栏

分析：每次只需要选取长度较小的两块板

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	//声明一个从小到大取出数值的优先队列
	priority_queue<int,vector<int>,greater<int>>que;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		int num;
		scanf("%d",&num);
		que.push(num);
	}
	long long ans=0;
	//直到队列中只剩下一个元素
	while(que.size()>1)
	{
		int l1=que.top();
		que.pop();
		int l2=que.top();
		que.pop();
		ans+=(l1+l2);
		que.push(l1+l2);
	}
	printf("%lld",ans);
	return 0;
}