-
我發現之前一版在電腦上看 常用函數部分 沒有問題,由于是手打上去的,在手機上看會發生錯位問題,現已將電腦原版 常用函數部分 截圖改為圖片形式,不會再發生錯位問題,非常感謝大家的支持
- ### priority_queue優先隊列出現頻率非常高,尤為重要(是一定要掌握的數據結構)
1.queue隊列
- queue是一種先進先出(FIFO)的數據結構
- queue提供了一組函數來操作和訪問元素,但它的功能相對較簡單
queue的定義和結構如下:?
template <class T, class Container = deque<T>>
class queue;- T:表示存儲在queue中的元素的類型。
- Container:表示底層容器的類型,默認為deque,也可以使用其他容器類型,如list
- queue的內部實現使用了底層容器來存儲元素,并且只能通過特定的函數來訪問和操作元素
以下是一些queue的常用函數:
### 這就像一個隊伍———————————————————————
pop出去 < —— 1 2 3 4 5 6 < —— push進來———————————————————————2.priority_queue優先序列
- priority_queue與普通的隊列不同,priority_queue中的元素是按照一定的優先級進行排序的
- 默認情況下,priority_queue按照元素的值的從大到小進行排序,即最大元素位于隊列的前面
priority_queue的定義和結構如下:
template <class T,Container=vector<T>,class Compare=less<typename Container::value_type>>
class priority_queue;- T:表示存儲在priority queue中的元素的類型
- Container:表示底層容器的類型,默認為vector,也可以使用其他容器類型,如deque
- Compare:表示元素之間的比較函數對象的類型,默認為less即按照元素的值進行比較
- priority_queue的內部實現使用了底層容器來存儲元素,并且只能通過特定的函數來訪問和操作元素
以下是一些priority_queue的常用函數：
### 介紹幾種優先隊列修改比較函數的方法
1.第一種
#include<bits/stdc++.h>
struct Compare{ //仿函數bool operator()(int a,int b){ //()重載 //自定義比較函數return a>b; //小根堆 }
};
int main(){std::priority_queue<int,std::vector<int>,Compare> pq;return 0;
}- 默認的是大根堆
2. 第二種
#include<bits/stdc++.h>
auto compare=[](int a,int b){//自定義比較函數,按照逆序排列return a>b;
};
int main(){std::priority_queue<int,std::vector<int>,decltype(compare)>pq(compare);return 0;
}- ?### 如果優先隊列中的元素類型比較簡單,可以直接使用greater<T>來修改比較方法
-
priority_queue<int,vector<int>,greaterr<int>> pq; //std::greater函數對象定義在<functional>頭文件中3.deque雙端隊列
- ?deque(雙端隊列)是一種容器,它允許在兩端進行高效的插入和刪除操作
- deque是由一系列連續的存儲塊(緩沖區)組成的,每個存儲塊都存儲了多個元素
- 這使得deque能夠在兩端進行快速的插入和刪除操作,而不需要移動其他元素
deque的定義和結構如下:
template <class T,class Allocator=allocator<T>>
class deque;- T:表示存儲在deaue中的元素的類型
- Allocator:表示用于分配內存的分配器類型,默認為allocator,deque的內部實現使用了一系列的存儲塊(緩沖區),每個存儲塊存儲了多個元素,并且通過指針進行連接
- 這種設計使得在兩端進行插入和刪除操作的時間復雜度為常數時間,即0(1)
###????????“單調隊列”將使用雙端隊列來實現(單純考察雙端隊列的并不常見)
以下是一些deque的函數：
- ### 10~12個并不常見?
4.例題講解:
題號:lanqiao OJ 1113?
1.CLZ銀行問題
#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int m;cin>>m;queue<string> V,N;while(m--){string op;cin>>op;//判斷是否為來到窗口//IN情況,推入nameif(op=="IN") {string name,q;cin>>name>>q;if(q=="V"){V.push(name);}else{N.push(name);} }//out情況,彈出nameelse{string q;cin>>q;if(q=="V"){V.pop();}else{N.pop();}} }//輸出VIP窗口namewhile(V.size()){cout<<V.front()<<"\n"; V.pop();} //輸出普通窗口namewhile(N.size()){cout<<N.front()<<"\n"; N.pop();} return 0;
}- ?每次都會彈出,隊列雖然是一種線性結構但它是不能遍歷的
題號:lanqiao OJ 741
2.合并果子
- ### 這里用到一點點貪心
- 1.先將1和2合并就消耗了3點體力,再將3和9合并就消耗了12點體力,共消耗15點體力
- 2.先將2和9合并就消耗了11點體力,再將1和11合并就消耗了12點體力,共消耗23點體力
- 方案1更省體力
- 那么思路就是每次找到一大堆數字中拿出來最小的兩個求和,再放回去(使用優先隊列)
- ### 這道題注意要開long long(int大概是2e9可能會超范圍)
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n;cin>>n; //這里直接用隊列就好了,沒必要再存數組里 priority_queue<ll,vector<ll>,greater<ll>> pq; //類型比較簡單,默認是大根堆,要的是小根堆把less直接改成greaterfor(int i=1;i<=n;++i){ll x;cin>>x;pq.push(x);} ll ans=0;while(pq.size()>=2){//這里pop出來兩個最小的數,也就是小根堆頂部的兩個數 ll x=pq.top();pq.pop();ll y=pq.top();pq.pop();ans+=x+y; //求和pq.push(x+y); //把最小數的和push回去 } cout<<ans<<"\n"; return 0;
}
