AcWing 839. 模拟堆
原题链接
简单
作者:
atsy
,
2021-05-08 16:55:39
,
所有人可见
,
阅读 366
map + priority_queue实现可以修改任意位置的堆
个人感觉手写堆除了提升一下自己码力,就没有啥用处了
在大多数情况下,我们只需要使用STL中的priority_queue即可,万不得已也可以手写左偏树
那么要修改任意位置,我自己瞎搞了一个优先级队列+map的方法,AC了本题,就是不知道有没有问题
希望各位小佬爷们帮忙康康
//ink代表第k个插入的是谁
//knum代表值为x的数有多少个
1.插入第cnt个数x, 常规操作聪明的你一定能看懂
ink[++cnt] = x;
knum[x] ++;
q.push(x);
2.删除集合中的最小值
问题在于我们集合中的最小值可能是已经被删除了的,那么我们需要找到一个最小值x,其knum[x] > 0,其余小于x的数弹出队列即可,然后找到之后
knum[x] --;
3.修改任意位置
直接把第k的插入的数x的个数减一
然后把k个插入的数改为x
然后把当前插入的数的个数加一
再把这个数插入优先级队列
其余操作都差不多,就留给各位观众思考了,有疑问可以在下方留言哈
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, cnt;
map<int, int> ink;
map<int, int> knum;
priority_queue<int, vector<int>, greater<int> > q;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i ++ ) {
string str;
int k, x;
cin >> str;
if (str == "I") {
cin >> x;
q.push(x);
ink[++cnt] = x;
knum[x] ++;
} else if (str == "PM") {
do {
x = q.top();
q.pop();
} while (!knum[x]);
q.push(x);
cout << x << '\n';
} else if (str == "DM") {
do {
x = q.top();
q.pop();
} while (!knum[x]);
knum[x] --;
} else if (str == "D") {
cin >> k;
x = ink[k];
knum[x] --;
} else {
cin >> k >> x;
knum[ink[k]] --;
ink[k] = x;
knum[x] ++;
q.push(x);
}
}
return 0;
}
感觉挺取巧的,算是一种lazy的思想
namo挺好写的