第8章 堆和 priority_queue（题目实战篇）

1P3378 【模板】堆1链接https://www.luogu.com.cn/problem/P33782题目3解析实现一个小根堆4代码stl#include iostream #include queue #include vector using namespace std; int main() { int n; cin n; priority_queueint, vectorint, greaterint q; while (n--) { int op; cin op; if (op 1) { int x; cin x; q.push(x); } else if (op 2) cout q.top() endl; else q.pop(); } return 0; }手推#includeiostream using namespace std; const int N 1e68; int n; int heap[N]; void up(int child){ int parent child/2; while(parent 1 heap[child]heap[parent]){ swap(heap[child],heap[parent]); child parent; parent child/2; } } void down (int parent ){ int child parent *2; while(child n){ if(child1n heap[child1]heap[child]) child; if(heap[child] heap[parent]) return; swap(heap[child],heap[parent]); parent child; child parent*2; } } void push(int x){ n; heap[n] x; up(n); } void pop(){ swap(heap[1],heap[n]); n--; down(1); } int main(){ int m;cin m; while(m--){ int op; cin op; if(op 1){ int x; cin x; push(x); } else if(op 2){ cout heap[1]endl; } else pop(); } return 0; }2第 k 小1链接第 k 小2题目3解析1题意理解用堆维护第K小topK问题2解题步骤1创大根堆2维护大根堆大小为K堆顶就是第K小4代码#includeiostream #includequeue using namespace std; priority_queueint heap; int main(){ int n,m,k; cin n m k; for(int i 1;in;i){ int x; cin x; heap.push(x); if(heap.size()k) heap.pop(); } while(m--){ int op; cin op; if(op 1){ int x;cinx; heap.push(x); if(heap.size()k) heap.pop(); } else{ if(heap.size() k) cout -1endl; else cout heap.top() endl; } } return 0; }3除21链接除22题目3解析用堆模拟实现tip:可以优化先全加后减去这样可以减少代码量4代码#includeiostream #includequeue using namespace std; typedef long long ll; const int N 1e54; priority_queueint q; int main(){ int n,k; cin n k; ll sum 0; for(int i 1;i n;i){ int x; cin x; sum x; if(x %2 0) q.push(x); } while(q.size() k--){ int m q.top()/2; q.pop(); sum - m; if(m % 2 0) q.push(m); } cout sum endl; return 0; }4P2085 最小函数值1链接https://www.luogu.com.cn/problem/P20852题目3解析解法堆二次函数单调性因为对称轴均在负半轴所以x0时单调递增-x1函数值算出来依次拿出最小的把对应的下一个函数值再算出来4代码#includeiostream #includequeue #includevector using namespace std; typedef long long ll; const ll N 1e48; ll a[N],b[N],c[N]; struct node{ ll f;//函数值 ll num;//函数编号 ll x;//代入值 bool operator (const node x) const{//运算符重载 return f x.f; } }; priority_queuenode heap; ll calc(ll i,ll x){//函数值 return a[i]*x*xb[i]*xc[i]; } int main(){ ll n,m; cin n m; for(ll i 1;i n;i){ cin a[i] b[i] c[i]; } //x 1 for(ll i 1;i n;i){ heap.push({calc(i,1),i,1}); } //依次拿m个值 while(m--){ auto t heap.top(); heap.pop(); ll f t.f,num t.num,x t.x; cout f ; heap.push({calc(num,x1),num,x1}); } return 0; }5P1631 序列合并1链接https://www.luogu.com.cn/problem/P16312题目3解析1a[i]b[1]2拿最小值-小根堆 - sum,a编号b编号把下一个和计算出来4代码#includeiostream #includequeue using namespace std; const int N 1e59; typedef long long ll; ll a[N],b[N]; struct node{ ll sum; int i,j; bool operator (const node x) const{ return sum x.sum; } }; priority_queuenode q; int main(){ int n;cin n; for(int i 1;i n;i) cin a[i]; for(int i 1;i n;i) cin b[i]; for(int i 1;i n;i) q.push({a[i]b[1],i,1}); for(int m 1; mn;m){ node t q.top();q.pop(); ll sum t.sum,i t.i,j t.j; cout sum ; if(j1n) q.push({a[i]b[j1],i,j1}); } return 0; }6P1878 舞蹈课1链接https://www.luogu.com.cn/problem/P18782题目3解析1,用priority_queue维护所有当前相邻异性对2,用pre[] / nxt[]模拟双向链表维护有人出列后的新相邻关系3,用deleted[]判断堆里的旧配对是否已经失效tip:难不是堆本身而是删除元素后怎么快速知道新的相邻关系所以需要pre[]和nxt[]模拟双向链表4代码#include iostream #include queue #include vector using namespace std; const int N 2e5 10; int n; char sex[N]; int a[N]; int pre[N], nxt[N]; bool deleted[N]; struct Node { int diff; int l, r; bool operator (const Node x) const { if (diff ! x.diff) return diff x.diff; return l x.l; } }; priority_queueNode pq; vectorpairint, int ans; int main() { cin n; for (int i 1; i n; i) { cin sex[i]; } for (int i 1; i n; i) { cin a[i]; pre[i] i - 1; nxt[i] i 1; } nxt[n] 0; for (int i 1; i n; i) { if (sex[i] ! sex[i 1]) { pq.push({abs(a[i] - a[i 1]), i, i 1}); } } while (!pq.empty()) { Node t pq.top(); pq.pop(); int l t.l; int r t.r; if (deleted[l] || deleted[r]) continue; if (nxt[l] ! r || pre[r] ! l) continue; ans.push_back({l, r}); deleted[l] deleted[r] true; int left pre[l]; int right nxt[r]; if (left) nxt[left] right; if (right) pre[right] left; if (left right sex[left] ! sex[right]) { pq.push({abs(a[left] - a[right]), left, right}); } } cout ans.size() \n; for (auto p : ans) { cout p.first p.second \n; } return 0; }