P1168 中位数

网址如下：P1168 中位数 - 洛谷 | 计算机科学教育新生态

一道求中位数的题，本来是想再用二分法来试一下的，但是出现了一点问题，先把AC的放出来

很简单，一个记录比中位数大的数的最小堆，和一个记录比中位数小的最大堆，每次插入一个元素的时候就可以完成快速的中位数转换，看struct的push函数就知道了，非常直观

代码如下：

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;

struct Mid{
    priority_queue<int, vector<int>, less<int>> max;
    priority_queue<int, vector<int>, greater<int>> min;
    int mid;
    int size;
    Mid():size(0), mid(0){}
    void push(int val){
        size++;
        if(val >= mid){
            min.push(val);
            if(size % 2){mid = min.top(); min.pop();}
            else{max.push(mid); mid = (max.top() + min.top()) / 2;}
        }
        else{
            max.push(val);
            if(size % 2){mid = max.top(); max.pop();}
            else{min.push(mid); mid = (max.top() + min.top()) / 2;}
        }
    }
}L;

int main(void)
{
    int N; scanf("%d", &N);
    for(int i = 1; i <= N; i++){
        int val; scanf("%d", &val);
        L.push(val);
        if(L.size % 2) printf("%d\n", L.mid);
    }

    return 0;
}

原文地址：https://blog.csdn.net/Fool256353/article/details/144034176

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！