海北藏族自治州网站建设_网站建设公司_网站建设_seo优化

priority_queue

优先队列，也叫"堆"，仅维护最大/最小元素，可以在较小的时间复杂度内获取某个元素集合的最大或最小值

优先队列常用于贪心、优化dp、构造、dijkstra、prim等问题或算法中，应用非常广泛

声明

//默认为大根堆

priority_queue<int> pq;

//改为小根堆

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

//比较复杂的结构，比如说pair和结构体等时使用自定义函数

//自定义比较函数常用方法

//方法一：全局函数，传入函数指针用decltype转换

bool cmp(const int &u,const int &v){

return u<u;

}

priority_queue<int, vector<int>,decltype(&cmp)> pq(cmp);

//方法二：匿名函数用cmp变量存储，传入变量

auto cmp = [](const int &u, const int &v){

return u<v;//大根堆

};

priority_queue<int,vector<int>,decltype(cmp)> pq(cmp);

//方法三：struct重载()运算符

struct cmp{

bool operator()(const int &u, const int &v){

return u<v;//大根堆

}

}

priority_queue<int,vector<int>,cmp> pq;

常规操作

//取出堆顶元素，时间复杂度为O(1)

cout << pq.top() << '\n';

//入堆，O(logn)，n为堆内元素个数

pq.push(x);

//出堆，O(logn)，n为堆内元素个数

pq.pop(); //注意保证pq非空

//获取堆内元素个数，即堆的大小

cout << pq.size() << '\n';

优先队列为树形结构，不支持遍历（除非逐个出堆）

小e吃松果

小e吃松果 | 星码StarryCoding 算法竞赛新手村

代码

#include<bits/stdc++.h> using namespace std; using ll = long long; int main(){ int n;cin>>n; priority_queue<ll,vector<ll>,greater<ll>> pq; for(int i=1;i<=n;i++){ ll x;cin>>x; pq.push(x); } ll ans=0; while(pq.size()>1){ ll x=pq.top();pq.pop(); ll y=pq.top();pq.pop(); ans+=x+y; pq.push(x+y); } cout << ans <<endl; return 0; }