AMIRIOX無暝 @ 2021-02-11 08:54:06
/kel 实在过不去了 这两份代码 所有点都WA 但能过样例
看OI-Wiki学的对顶堆 然而看题解发现好像代码都很不一样
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
int n;
priority_queue<int, vector<int>, greater<int> > small;
priority_queue<int, vector<int>, less<int> > big;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
if (!big.empty() && x <= big.top()) {
big.push(x);
} else {
small.push(x);
}
if (i % 2) {
printf("%d\n", small.top());
}
if (small.size() < (small.size() + big.size() + 1) / 2) {
small.push(big.top());
big.pop();
} else if (small.size() > (small.size() + big.size() + 1) / 2) {
big.push(small.top());
small.pop();
}
}
return 0;
}
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
int n, x;
priority_queue<int, vector<int>, greater<int> > small;
priority_queue<int, vector<int>, less<int> > big;
int main() {
scanf("%d", &n);
scanf("%d", &x);
small.push(x);
printf("%d\n", x);
for (int i = 2; i <= n; i++) {
scanf("%d", &x);
if (i % 2 && i != n) {
printf("%d\n", small.top());
} else if (i % 2 && i == n) {
printf("%d", small.top());
}
if (!big.empty() && x <= big.top()) {
big.push(x);
} else {
small.push(x);
}
if (small.size() < (small.size() + big.size() + 1) / 2) {
small.push(big.top());
big.pop();
} else if (small.size() > (small.size() + big.size() + 1) / 2) {
big.push(small.top());
small.pop();
}
}
return 0;
}
by Alan_Zhao @ 2021-02-11 09:54:10
vector 上的常见操作复杂度(效率)如下:
随机访问——常数 ?(1)
在末尾插入或移除元素——均摊常数 ?(1)
插入或移除元素——与到 vector 结尾的距离成线性 ?(n)
——cppreference
by Alan_Zhao @ 2021-02-11 09:55:23
里面的 O 没显示出来……
by brimosta @ 2021-02-11 10:13:52
@BreakPlus 话说vector是线性的,插入应该是O(n)
但是跑的飞快qwq
by brimosta @ 2021-02-11 10:14:25
直播获奖就可以用vector做
by AMIRIOX無暝 @ 2021-02-11 10:23:22
@BreakPlus 问题是我正在学习对顶堆啊...这不是对顶堆模板吗
by AMIRIOX無暝 @ 2021-02-11 10:25:07
@cmll02 谢谢大佬!我实属脑残
by 白鲟 @ 2021-02-11 10:37:08
@BreakPlus @SIXIANG 拿小常数
by SIXIANG32 @ 2021-02-11 10:51:16
@白鲟 害不是
by 白鲟 @ 2021-02-11 10:54:32
@SIXIANG vector
会那么良心吗
by Christophe_ @ 2022-07-24 00:09:04
@Little_Sealx 理论时间复杂度