1.模版堆
P3378 【模板】堆 - 洛谷
#include <iostream>#include <queue>using namespace std;int n, m, k;
priority_queue<int> heap; // 默认就是⼤根堆 int main()
{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(op == 2) // 查询第 k ⼩ {if(heap.size() == k) cout << heap.top() << endl;else cout << -1 << endl;}}return 0;
}
2.第k小
第 k 小
//第k小，创建大根堆，限制堆的大小，大的不插入，最后输出最后一个
#include<iostream>
#include<queue>using namespace std;int n, m, k;int main()
{priority_queue<int> q;cin >> n >> m >> k;while (n--){int x; cin >> x;/*if (q.size() < k){q.push(x);}else if(x < q.top()){q.pop();q.push(x);}*/q.push(x);if (q.size() > k)q.pop();}//执行操作while (m--){int op; cin >> op;if (op == 1){int x; cin >> x;/*if (q.size() < k){q.push(x);}else if (x < q.top()){q.pop();q.push(x);}*/q.push(x);if (q.size() > k)q.pop();}else if (op == 2){if (q.size() < k){cout << -1 << endl;continue;}cout << q.top() << endl;}}return 0;
}3.除2！
除2！
#include<iostream>
#include<queue>using namespace std;int n, k;
typedef long long LL;
LL sum = 0;int main()
{cin >> n >> k;priority_queue<int> heap;//默认大堆while (n--){int x;cin >> x; sum += x;if (x % 2 == 0)heap.push(x);}while (heap.size() && k--){int t = heap.top() / 2;heap.pop();sum -= t;if (t % 2 == 0)heap.push(t);}cout << sum << endl;
}4.最小函数值
P2085 最小函数值 - 洛谷
#include<iostream>
#include<queue>using namespace std;
int n, m;
const int N = 1e4 + 10;
int a[N], b[N],c[N];
typedef long long LL;struct node
{LL f;//函数值int num;//函数编号int x;//代入值//建立小堆bool operator <(const node& x)const{return f > x.f;//通过函数值进行比较}
};priority_queue<node> heap;//计算值
LL cal(int i, int x)
{return a[i] * x * x + b[i] * x + c[i];
}int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){cin >> a[i] >> b[i] >> c[i];}int x = 1;for (int i = 1; i <= n; i++){heap.push({ cal(i,1),i,1 });}while (m--){auto v = heap.top(); heap.pop();int f = v.f, num = v.num, x = v.x;cout << f << " ";//输出当前最小值//把下一个值推入进去heap.push({ cal(num,x+1),num,x+1 });}return 0;
}5.序列合并网有点问题
P1631 序列合并 - 洛谷
#include<iostream>
#include<queue>using namespace std;int n;
const int N = 1e5 + 10;
int a[N], b[N];
typedef long long LL;struct node
{int sum = 0;int ai = 1;int bj = 1;bool operator < (const node& x)const//建立小堆{return sum > x.sum;}
};
priority_queue<node> heap;int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 1; i <= n; i++){cin >> b[i];}//把a[i]+b[1]录进去for (int i = 1; i <= n; i++){heap.push({ a[i]+b[1],i,1});}int m = n;while (m--){auto v = heap.top(); heap.pop();int sum = v.sum; int ai = v.ai; int bj = v.bj;cout << sum << " ";if(bj+1<=n)heap.push({ a[ai]+b[bj+1],ai,bj + 1});}return 0;
}6.舞蹈课
记录详情 - 洛谷 | 计算机科学教育新生态
#include<iostream>
#include<queue>
#include<vector>
#include<math.h>using namespace std;const int N = 2e5 + 10;int n;//人数
int s[N];//标记男女//使用双向链表，方便链接
int e[N];//由于有顺序，不需要id h
int pre[N], ne[N];bool st[N];//标记是否已出队列struct node
{int dif;int l, r;//重写<,小根堆bool operator < (const node& x)const{if (dif != x.dif)return dif > x.dif;else if (l != x.l)return l > x.l;else return r > x.r;//最左边先行}
};priority_queue<node> heap;int main()
{cin >> n;for (int i = 1; i <= n; i++){char alp;cin >> alp;if (alp == 'B')s[i] = 1;//标记男为1，女为0}//输入参数值cin >> e[1]; ne[1] = 2,pre[1] = 0;//标记前后for (int i = 2; i <= n; i++){cin >> e[i];//标记前后pre[i] = i - 1;ne[i] = i + 1;//推入nodeif (s[i] != s[i - 1])//异性推入heap.push({ abs(e[i] - e[i - 1]),i - 1,i });}pre[n] = n - 1;ne[n] = 0;vector<node> res;//用于输出while (heap.size()){auto t = heap.top();//取出顶部heap.pop();int dif = t.dif, l = t.l, r = t.r;//判断是否已经出列if (st[l] || st[r])continue;//都没有出列,推入resres.push_back({ abs(e[l] - e[r]),l,r }); st[l] = true, st[r] = true;//把断的地方链接起来ne[pre[l]] = ne[r];pre[ne[r]] = pre[l];//把相连的地方推入heap中int left = pre[l], right = ne[r];if (left && right && s[left] != s[right]){heap.push({ abs(e[left] - e[right]),left,right });}}//输出结果cout << res.size() << endl;for (auto& x : res){cout << x.l << " " << x.r << endl;}return 0;
}使用了双向链表：用于链接两边
堆（priority_queue）：用来找出最小的
bool st[N]标记是否出列
