题解 P1168 【中位数】

张小源 · 2016-11-16 18:33:51 · 题解

这题可以用两个堆做。。。左堆为大根堆右堆，为小根堆，遇到大于大根堆堆顶的就放在小根堆里。。。反之放入大根堆。。让他们的元素个数差值为一，如果不为一就从多的一个拿出来放入少的一个中。。。之后元素多的堆顶的元素就是中位数了。。哈哈。。下面是代码

 #include<cstdio>
#include<iostream>
#include<queue>
#include<cmath>
#include<algorithm>
#include<ctime>
using namespace std;
inline int read()
{
    char ch=getchar();
    int a=0,t=1;
    while(ch<'0'||ch>'9') {if(ch=='-') t=-1;ch=getchar();}
    while(ch<='9'&&ch>='0') {a=a*10+ch-'0';ch=getchar();}
    return a*t;
}
priority_queue<int,vector<int> > l;
priority_queue<int,vector<int>,greater<int> > r;
int n;
int num=0;
int leftnum=0,rightnum=0;
int x,y;
int a[5000001];
int main()
{
    //int th=clock();
    freopen("wq.in","r",stdin);freopen("wq.out","w",stdout);
    n=read();
    //l.resize(1000001);r.resize(1000001);
    a[1]=read();a[2]=read();a[3]=read();
    printf("%d\n",a[1]);
    sort(a+1,a+4);
    printf("%d\n",a[2]);
    l.push(a[1]);leftnum++;
    l.push(a[2]);leftnum++;
    r.push(a[3]);rightnum++;
    for(int q=5;q<=n;q+=2)
    {
        for(int i=q-1;i<=q;++i)
        {
            a[i]=read();
            //if(l.empty()==1) {l.push(a[i]);leftnum++;continue;}
            //if(r.empty()==1) {r.push(a[i]);rightnum++;continue;}
            x=l.top();y=r.top();
            int bo=0;
            if(a[i]<=x) {l.push(a[i]),leftnum++,bo=1;continue;}
            if(a[i]>=y) {r.push(a[i]),rightnum++,bo=1;continue;}
            if(a[i]>x) {r.push(a[i]),rightnum++,bo=1;continue;}
            if(a[i]<y) {l.push(a[i]),leftnum++,bo=1;continue;}
            //if(bo==0) l.push(a[i]),leftnum++;
        }
        while(abs(leftnum-rightnum)!=1)
        {
            if(leftnum>rightnum)
            {
                x=l.top();
                l.pop();
                leftnum--;
                r.push(x);
                rightnum++;
                continue;
            }
            if(leftnum<rightnum)
            {
                x=r.top();
                r.pop();
                rightnum--;
                l.push(x);
                leftnum++;
                continue;
            }
        }
        if(leftnum>rightnum) 
        {
            x=l.top();
            //num++;
            printf("%d\n",x);
            continue;
        } 
        if(leftnum<rightnum) 
        {
            //num++;
            x=r.top();
            printf("%d\n",x);
            continue;
        }
    } 
    //while(l.empty()!=0)
    //printf("%d",th-clock());
    //printf("%d",num);
    return 0;
}