luogu P1168 中位数

题目描述

给出一个长度为NN的非负整数序列A_i，对于所有1 ≤ k ≤ (N + 1) / 21≤k≤(N+1)/2，输出A_1, A_3, …, A_2k - 1的中位数。即前1,3,5,…个数的中位数。

输入格式

第1行为一个正整数N，表示了序列长度。

第2行包含N个非负整数A_i (A_i ≤ 10^9)

输出格式

共(N + 1) / 2(N+1)/2行，第ii行为A_1, A_3, …, A_2k - 1 的中位数。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N],b[N],c[N], n;
bool vis[N];
inline void add(int x,int y){
    for(;x<N;x+=x&(-x))c[x]+=y;
}
inline int sum(int x){
    int ans=0;
    for(;x;x-=x&(-x))ans+=c[x];
    return ans;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++){
        int op=lower_bound(b+1,b+1+n,a[i])-b;
        while(vis[op])op++;
        vis[op]=1;
        a[i]=op;
    }
    for(int i=1;i<=n;i++){
        add(a[i],1);
        if(!(i&1))continue;
        int l=0,r=n,ans=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(sum(mid-1)<=sum(n+1)-sum(mid)){
                l=mid+1;
                ans=mid;
            }else r=mid-1;
        }
        cout<<b[ans]<<endl;
    }
}

luogu P1168 中位数

原文：https://www.cnblogs.com/naruto-mzx/p/11857523.html