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

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 AMIRIOX無暝 @ 2021-02-11 09:00:48

（第二份代码不用看了知道错哪了 i=3的时候输出在前此时只有两个数字

但是第一份代码不知道怎么错了

by BreakPlus @ 2021-02-11 09:26:25

@AMIRIOX無暝给你个东西告别手写堆、对顶堆

vector<int>vec;
void sort_push(int f)
{
    vec.insert(upper_bound(vec.begin(),vec.end(),f),f);
}

by SIXIANG32 @ 2021-02-11 09:30:28

@AMIRIOX無暝告诉你有一个叫 vector 的东西，好用极了，而且常数比 STL 的 priority_queue 快亿倍

by cmll02 @ 2021-02-11 09:32:11

@AMIRIOX無暝把输出放到后面去

by cmll02 @ 2021-02-11 09:32:47

#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 (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();
        }
        if (i % 2) {
            printf("%d\n", small.top());
        }
    }
    return 0;
}

by Alan_Zhao @ 2021-02-11 09:33:34

@SIXIANG @BreakPlus 然而这题数据范围开大点 vector 就过不去了

by Remake_ @ 2021-02-11 09:34:19

@SIXIANG 快亿倍，你确定？

by w23c3c3 @ 2021-02-11 09:41:44

不懂就问，这个vector不是O(n)的吗

by SIXIANG32 @ 2021-02-11 09:49:02

@Miracle_Creator 运用了夸张的修辞手法，夸张化了 vector 的常数，使人更加清晰的感受到了 vector 常数之小。（滑稽

by SIXIANG32 @ 2021-02-11 09:49:22

@w23c3c3 我记得是 \sqrt{n} 的吧/jk

| 下一页