洛谷P1168 中位数—

先上一波链接 https://www.luogu.com.cn/problem/P1168

这道题我们有两种写法

第一种呢是线段树，我们首先需要将原本的数据离散化，线段树维护的信息就是区间内有多少个数，

每次加入两个数（也就是单点修改），查询的时候就是查找中位数（（x+1）/2 ）所在的位置

每次走到一个点判断左子树中数字的个数（y）是不是就大于等于当前所找的数k 如果是则往左子树继续走

如果左子树的数字个数（y）小于当前所找的数k，那么就将k减去y，再往右子树走，这样一直走下去就可以找到中位数所在的位置

然后再将其位置所对应的离散化前对应的点输出来就可以了这样的复杂度是O（nlogn）的

贴一手代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
const int M=1e6+7;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
struct qwq{int w,id;}s[M];
int n,xs[M],xp,fr[M];
struct node{int l,r,sum;}e[M];
void build(int x,int l,int r){
    e[x].l=l; e[x].r=r;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1^1,mid+1,r);
}
void up(int x){e[x].sum=e[x<<1].sum+e[x<<1^1].sum;}
void ins(int x,int k){
    if(e[x].l==e[x].r){
        e[x].sum++;
        return ;
    }
    int mid=(e[x].l+e[x].r)>>1;
    if(k<=mid) ins(x<<1,k);
    else ins(x<<1^1,k);
    up(x);
}
int find(int x,int S){
    if(e[x].l==e[x].r) return e[x].l;
    if(e[x<<1].sum>=S) return find(x<<1,S);
    return find(x<<1^1,S-e[x<<1].sum);
}
int cnt=1;
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        s[i].w=read();
        xs[++xp]=s[i].w;
    }
    sort(xs+1,xs+1+xp);
    for(int i=1;i<=n;i++){
        int now=lower_bound(xs+1,xs+xp+1,s[i].w)-xs;
        s[i].id=now; fr[now]=s[i].w;
    }
//    for(int i=1;i<=n;i++) printf("%d ",s[i].id); puts("");
//    for(int i=1;i<=n;i++) printf("%d ",fr[i]); puts("");
    build(1,1,n);
    ins(1,s[1].id);
    for(int i=1;i<=n;i+=2){
        int ans=find(1,(i+1)/2);
        printf("%d\n",fr[ans]);
        ins(1,s[++cnt].id);
        ins(1,s[++cnt].id);
    }
    return 0;
}

View Code

另一种做法就是用multiset维护，我们将迭代器It 始终指向中位数，每次插入两个数

如果两个数都比他大，就将It++，因为此时中位数在当前 It 所在位置的后一位了

同理如果两个数都比他小，就将 It--，如果一大一小，那么中位数位置不变，这样就圆满解决了问题

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<set>
using namespace std;
const int M=1e6+7;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
int n,s[M],ans[M];
multiset<int>S; 
multiset<int>::iterator It; 
int main(){
    //freopen("1.in","r",stdin);
    n=read(); for(int i=1;i<=n;i++) s[i]=read();
    S.insert(s[1]); 
    It=S.lower_bound(s[1]);
    int cnt=1;
    for(int i=1;i<=(n+1)/2;i++){
        ans[i]=*It;
        S.insert(s[++cnt]);
        S.insert(s[++cnt]);
        if(s[cnt]>=*It&&s[cnt-1]>=*It) ++It;
        else if(s[cnt]<*It&&s[cnt-1]<*It) --It;
        printf("%d\n",ans[i]);
    }
    return 0;
}

View Code

洛谷P1168 中位数——set/线段树

推荐阅读