赤坎手机网站建设公司,全托管跨境电商平台有哪些,深圳市电子商务有限公司,电商工作计划怎么写模拟堆
维护一个集合#xff0c;初始集合为空#xff0c;支持如下几种操作#xff1a; 1.“I x”#xff0c;插入一个数x 2.“PM” #xff0c;输出当前集合中的最小值 3.“DM”#xff0c;删除当前集合中的最小值#xff08;当最小值不唯一时#xff0c;删除最早插入…模拟堆
维护一个集合初始集合为空支持如下几种操作 1.“I x”插入一个数x 2.“PM” 输出当前集合中的最小值 3.“DM”删除当前集合中的最小值当最小值不唯一时删除最早插入的最小值 4.“D k”删除第k个插入的数 5.“C k x”修改第k个插入的数将其变为x 现在要进行N次操作对于所有的第2个操作输出当前集合的最小值
输入格式
第一行包含整数N 接下来N行每行包含一个操作指令操作指令I x“PM”“DM”D k或C k x中的一种
输出格式
对于每个输出指令PM输出一个结果表示当前集合中的最小值 每个结果占一行
数据范围 1 ≤ N ≤ 1 0 5 1\le N\le 10^5 1≤N≤105 − 1 0 9 ≤ x ≤ 1 0 9 -10^9\le x\le 10^9 −109≤x≤109 数据保证合法
输入样例 10 I -10 PM I -10 D 1 C 2 8 I 6 PM DM 输出样例 -10 6 AC代码
#includeiostream
#includecstring
#includealgorithm
using namespace std;const int N 1e5 10;int n, m;
int h[N], ph[N], hp[N], sz;void heap_swap(int a, int b) {swap(ph[hp[a]], ph[hp[b]]);swap(hp[a], hp[b]);swap(h[a], h[b]);
}void down(int u) {int t u; if(u * 2 sz h[u * 2] h[t]) t u * 2;if(u * 2 1 sz h[u * 2 1] h[t]) t u * 2 1 ;if(u ! t) {heap_swap(u, t);down(t);}
}void up(int u) {while(u / 2 h[u / 2] h[u]) {heap_swap(u / 2, u);u / 2;}
}int main() {scanf(%d, n);while(n--) {char op[10];int k, x;scanf(%s, op);if(op[0] I) {scanf(%d, x);sz, m;ph[m] sz, hp[sz] m;h[sz] x;up(sz);} else if(!strcmp(op, PM)) printf(%d\n, h[1]);else if(!strcmp(op, DM)) {heap_swap(1, sz);sz--;down(1);} else if(op[0] D) {scanf(%d, k);k ph[k];heap_swap(k, sz);sz--;down(k), up(k);} else {scanf(%d%d, k, x);k ph[k];h[k] x;down(k), up(k);}}return 0;
}
