|洛谷|堆|P1168 中位数-白红宇

|洛谷|堆|P1168 中位数

阅读量：4613 次

发布时间：2019-06-09

本文共 810 字，大约阅读时间需要 2 分钟。

https://www.luogu.org/problem/show?pid=1168

维护两个堆，一个大根堆L维护小于等于mid的数，一个小根堆R维护大于等于mid的数，mid是上次输出的中位数

然后进行调整即可

#include
    
     #include
     
      #include
      
       #include
       
        #define ms(i,j) memset(i,j, sizeof i);using namespace std;int n;priority_queue
        
          L;//bigpriority_queue

, greater

> R;//smallint main(){ scanf("%d",&n); int x1,x2; scanf("%d", &x1); R.push(x1); int mid = x1; printf("%d\n", mid); for (int i=1;i<=(n+1)/2-1;i++) { scanf("%d%d", &x1, &x2); if (x1<=mid) L.push(x1); else R.push(x1); if (x2<=mid) L.push(x2); else R.push(x2); while (L.size() >= R.size()) {R.push(L.top()); L.pop();} while (L.size() < R.size()-1) {L.push(R.top()); R.pop();} printf("%d\n", R.top()); mid = R.top(); } return 0;}

转载于:https://www.cnblogs.com/flyinthesky1/p/6384241.html

你可能感兴趣的文章