nowcoder172A 中位数 (二分答案)

时间:2024-10-15 11:07:15

二分一下答案,假设是x。

我们把大于x的看成1,小于x的看成-1,等于x的看成0

那某个区间的和如果是正的,就说明这个区间中位数大于x;如果是0,就等于x;如果是负的,就小于x;

这样的话,做一个前缀和,然后维护一下满足长度>=len的最小值,然后减一减,看看是不是>=0就可以了。

(我自己写的话我自己都看不懂...)

 #include<bits/stdc++.h>
#define pa pair<int,int>
#define ll long long
using namespace std;
const int maxn=; ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int N,num[maxn],val[maxn],mlen;
int sum[maxn]; inline bool judge(int x){
for(int i=;i<=N;i++) sum[i]=sum[i-]+(num[i]<x?-:num[i]>x);
int mi=0x3f3f3f3f;bool b=;
for(int i=mlen+;i<=N;i++){
mi=min(mi,sum[i-mlen]);
b|=(sum[i]>=mi);
}return b;
} int main(){
int i,j,k;
N=rd(),mlen=rd();
for(i=;i<=N;i++) val[i]=num[i]=rd();
sort(val+,val+N+);
int l=,r=N;
while(l<=r){
int m=l+r>>;
if(judge(val[m])) l=m+;
else r=m-;
}printf("%d\n",val[l-]);
return ;
}