靠,大过年的还得发个对顶堆的求助贴

P1168 中位数

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


上一页 |