CF1486D Max Median
题目链接:CF1486D Max Median
题目描述
有一个长度为 n 的数组,找出 所有长度至少为 k 的子段 的 最大的中位数
如果一个数组 a 长度为 n ,且按照递增顺序排列。那么 \lfloor\frac{n+1}{2} \rfloor 位置上的数是这个数组的中位数。
Solution
自己想怎么也做不出来,看了题解才会
先是看了一个提示:How to solve the problem if all the values are −1 and 1? 。。然鹅还是不太会,但这个提示可以说是做法的核心了。
我们将问题转化,转化为验证答案是否能大于等于 x ,可以发现这个问题的答案是具有单调性的,那么就可以二分。
我们将序列中 小于 x 的数设置为 -1 ,大于等于 x 的值设置为 1 。
可以发现,如果一个子段的序列和为正数,那么这个子段的中位数一定是大于等于 x 的。
因为 \ge x 的数比 \le x 的数多,所以 \lfloor\frac{n+1}{2} \rfloor 这个位置上的数一定是 \ge x 的。
然后可以利用前缀和在 O(n) 的复杂度内算出子段最大和,检验它是否大于 1 即可。
复杂度 O(nlogn)
真是妙啊。。。问题 **中位数为 x ** 的答案不一定具有单调性,但是问题 **中位数是否大于等于 x ** 的答案就具有单调性。。然后转化了一下,验证也变的简单了。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int n,k;
int a[N];
pair<int,int> p[N];
int q[N];
int check(int x){
int m=0;
q[0]=0;
for(int i=1;i<=k;++i)
if(a[i]<x) q[i]=q[i-1]-1;
else q[i]=q[i-1]+1;
if(q[k]>0) return 1;
for(int i=k+1;i<=n;++i){
if(a[i]<x) q[i]=q[i-1]-1;
else q[i]=q[i-1]+1;
m=std::min(m,q[i-k]);
if(q[i]-m>0) return 1;
}
return 0;
}
int main(){
scanf("%d %d",&n,&k);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
int l=1,r=n<<3;
while(l+1<r){
int mid = l + r >>1;
if(check(mid)) l=mid;
else r=mid;
}
printf("%d",l);
}
0 条评论