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

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 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 拿小常数 \operatorname{O}(n) 误导他人是不太道德的行为罢


by SIXIANG32 @ 2021-02-11 10:51:16

@白鲟 害不是 O(\sqrt{n}) 的吗?/jk/jk/jk/jk/jk


by 白鲟 @ 2021-02-11 10:54:32

@SIXIANG vector 会那么良心吗


by Christophe_ @ 2022-07-24 00:09:04

@Little_Sealx 理论时间复杂度 O(n),不过常数极小,实际运行效率接近块状链表 O(\sqrt{n}) qwq


上一页 | 下一页