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 SIXIANG32 @ 2022-07-24 18:05:53
@【Diana】 qwq 居然有人翻出了我的早期言论 qaq
不过还是感谢居然花心思回了我 qwq