题解：CF2128E1 Submedians (Easy Version)

vanueber · 2025-08-12 13:24:19 · 题解

模拟赛签到题。

做过 P2839 [国家集训队] middle ，中位数的经典套路。

考虑二分答案 v，将数组中 <v 的数设为 -1，\ge v 的数设为 1，一个区间 [l,r] 合法当且仅当 \sum_{i=l}^{r} a_i \ge 0。

二分的检查函数返回中位数是否 \le mid，检查时为了满足 r-l+1\ge k，从 r=k 开始枚举，为了满足 pre_r-pre_{l-1} \ge 0，显然 pre_{l-1} 取到的是一段前缀最小值，最后记录答案就做完了。

#include <bits/stdc++.h>
#define umap unordered_map
#define vint vector<int>
#define ll long long
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define ull unsigned long long
#define uint unsigned int
#define rg register
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define sqr(x) ((x)*(x))
using namespace std;
const int INF=0x3f3f3f3f;
inline int read(){
    int w=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        w=(w<<1)+(w<<3)+(ch^48);
        ch=getchar();
    }
    return w*f;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

const int N=3e5+10;
int n,k,a[N],T,b[N],pre[N];
int vmax=0,L=0,R=0;
bool check(int x){
    bool flag=0;
    for(int i=1;i<=n;++i) b[i]=(a[i]<x?-1:1);
    for(int i=1;i<=n;++i) pre[i]=pre[i-1]+b[i];
    int pre_min=0,pos=0;
    for(int i=k;i<=n;++i){
        if(pre[i-k]<pre_min){
            pre_min=pre[i-k],pos=i-k;
        }
        if(pre[i]-pre_min>=0){
            flag=1,L=pos+1,R=i;
        }
    }
    if(flag) vmax=max(vmax,x);
    return flag;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    cin>>T;
    while(T--){
        cin>>n>>k;
        rep(i,1,n) a[i]=read();
        int l=1,r=n;
        vmax=L=R=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(mid)){
                l=mid+1;
            }
            else{
                r=mid-1;
            }
        }
        cout<<vmax<<" "<<L<<" "<<R<<"\n";
    }
    #ifndef ONLINE_JUDGE
    fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
    #endif
    return 0;
}