企业官网建设流程全解析

1，P3378 【模板】堆

1，链接

https://www.luogu.com.cn/problem/P3378

2，题目

3，解析

实现一个小根堆

4，代码

stl

#include <iostream> #include <queue> #include <vector> using namespace std; int main() { int n; cin >> n; priority_queue<int, vector<int>, greater<int>> 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; }

手推

#include<iostream> using namespace std; const int N = 1e6+8; 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(child+1<=n && heap[child+1]<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，代码

#include<iostream> #include<queue> using namespace std; priority_queue<int> heap; int main(){ int n,m,k; cin >> n >> m >>k; for(int i = 1;i<=n;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;cin>>x; heap.push(x); if(heap.size()>k) heap.pop(); } else{ if(heap.size() < k) cout << -1<<endl; else cout << heap.top() << endl; } } return 0; }

3，除2！

1，链接

除2！

2，题目

3，解析

用堆模拟实现

tip:可以优化：先全加后减去，这样可以减少代码量

4，代码

#include<iostream> #include<queue> using namespace std; typedef long long ll; const int N = 1e5+4; priority_queue<int> 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; }

4，P2085 最小函数值

1，链接

https://www.luogu.com.cn/problem/P2085

2，题目

3，解析

解法

堆＋二次函数单调性

因为对称轴均在负半轴，所以x>0时，单调递增

->

x=1函数值算出来，

依次拿出最小的，把对应的下一个函数值再算出来

4，代码

#include<iostream> #include<queue> #include<vector> using namespace std; typedef long long ll; const ll N = 1e4+8; 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_queue<node> heap; ll calc(ll i,ll x){//函数值 return a[i]*x*x+b[i]*x+c[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,x+1),num,x+1}); } return 0; }

5，P1631 序列合并

1，链接

https://www.luogu.com.cn/problem/P1631

2，题目

3，解析

1，a[i]+b[1]

2，拿最小值（->小根堆 -> <sum,a编号，b编号>），把下一个和计算出来

4，代码

#include<iostream> #include<queue> using namespace std; const int N = 1e5+9; 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_queue<node> 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; m<=n;m++){ node t = q.top();q.pop(); ll sum = t.sum,i = t.i,j = t.j; cout << sum << " "; if(j+1<=n) q.push({a[i]+b[j+1],i,j+1}); } return 0; }

6，P1878 舞蹈课

1，链接

https://www.luogu.com.cn/problem/P1878

2，题目

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_queue<Node> pq; vector<pair<int, 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; }