P1168 中位数

传送门

思路：

1.对顶堆，大根堆(从大到小)存较小的数，小根堆(从小到大)存较大的数。

如果当前数大于大根堆顶，就放入小根堆，否则放入大根堆。

然后维护使两堆容量大小之差小于等于1，然后容量较大的那个堆顶元素即是答案。

因为题目保证是求奇数个数的中位数，显然比中位数小的个数=比中位数大的个数，所以取多了那一个的堆顶即可。

时间复杂度：。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
priority_queue<int>q1;    //大根堆 
priority_queue<int,vector<int>,greater<int> >q2;//小根堆 
int main(){
    int  n,x; 
    scanf("%d%d",&n,&x);q1.push(x);
    printf("%d\n",x);
    for(int i=2;i<=n;i++){
        scanf("%d",&x);
        if(x>q1.top()) q2.push(x);
        else q1.push(x);
        while(abs((int)q1.size()-(int)q2.size())>1){
            if(q1.size()>q2.size()) q2.push(q1.top()),q1.pop();
            else q1.push(q2.top()),q2.pop();
        }
        if(i&1){
            if(q1.size()>q2.size()) printf("%d\n",q1.top());
            else printf("%d\n",q2.top());
        }
    }
    return 0;
}

2.权值树状数组离散化+二分。

找中位数即是找第小的数。

显然我们可以二分枚举权值的大小是多少，即最大值最小化，大于等于的权值最小化即使权值答案，然后输出权值对于的元素即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
#define lowbit(x) x&(-x)
int n,tr[N],cnt,a[N],b[N];
void add(int x,int v){
    while(x<=cnt) tr[x]+=v,x+=lowbit(x);
}
int sum(int x){
    int ans=0;
    while(x){
        ans+=tr[x];
        x-=lowbit(x);
    }
    return ans;
} 
int Find(int x){
    int l=1,r=cnt;
    while(l<=r){
        int mid=(l+r)>>1; 
        if(sum(mid)>=x) r=mid-1;
        else l=mid+1;
    }
    return b[l];
}
int main(){    
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+n+1);
    cnt=unique(b+1,b+n+1)-(b+1);
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
    for(int i=1;i<=n;i++){
        add(a[i],1);
        if(i&1) printf("%d\n",Find((i+1)/2));
    }
    return 0;
}

3.对于第二种方式还可以用倍增法找权值，倒序枚举权值的位，找到小于的最大，答案就是。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
#define lowbit(x) x&(-x)
int n,tr[N],cnt,a[N],b[N];
void add(int x,int v){
    while(x<=cnt) tr[x]+=v,x+=lowbit(x);
}

int fun(int k){
    int id=0,sum=0;
    for(int i=20;i>=0;i--){
        id+=(1<<i);
        if(id>cnt||sum+tr[id]>=k) id-=(1<<i);
        else sum+=tr[id];
    }
    return b[id+1];
}
int main(){    
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+n+1);
    cnt=unique(b+1,b+n+1)-(b+1);
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
    for(int i=1;i<=n;i++){
        add(a[i],1);
        if(i&1) printf("%d\n",fun((i+1)/2));
    }
    return 0;
}