D. Max Median 二分 + 思维

D. Max Median 二分 + 思维

题目大意：

给你一个长度为n的序列，一个长度为 x 的中位数是 这个序列重新排序之后的 \(\frac{x+1}{2}\) 向下取整的位置，让你求长度至少为 \(k\) 的子序列的最大中位数是多少？

题解：

• 这个是有一个单调性的，所以可以二分这个值
• 因为长度是至少为 \(k\) ，而 \(k\) 的数据范围又和 \(n\) 差不多，所以如果不能双指针的话，那么最后一定可以按照某个结论转化成长度为 \(k\)
• 假设最大中位数是大于等于 \(x\) ，那么我如何判断是否成立呢？
• 首先我把所有大于等于 \(x\) 的值设为 1，小于的设为 -1，判断 \(i\) 这个位置是否可行，就只需要找到 \([1,i-k]\) 这个位置的前缀和最小值即可，如果 \(pre[i] - premin[i-k]>0\) 即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
int pre[maxn],premin[maxn],n,k,a[maxn];
bool check(int x){
    for(int i=1;i<=n;i++){
        if(a[i]>=x) pre[i] = pre[i-1] + 1;
        else pre[i] = pre[i-1] - 1;
        premin[i] = min(premin[i-1],pre[i]);
    }
    for(int i=k;i<=n;i++){
        if(pre[i]-premin[i-k]>0) return true;
    }
    return false;
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int l = 1,r = n,ans = 1;
    while(l<=r){
        int mid = (l+r)>>1;
        if(check(mid)) l = mid+1,ans = mid;
        else r = mid - 1;
    }
    printf("%d\n",ans);
    return 0;
}

D. Max Median 二分 + 思维

原文：https://www.cnblogs.com/EchoZQN/p/14490232.html