专栏文章

题解：CF2128E1 Submedians (Easy Version)

vvanueber
CF2128E1题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miodlwzu
此快照首次捕获于
2025/12/02 17:28
3 个月前
此快照最后确认于
2025/12/02 17:28
3 个月前
查看原文
模拟赛签到题。
做过 P2839 [国家集训队] middle ，中位数的经典套路。
考虑二分答案 vv，将数组中 <v<v 的数设为 −1-1，≥v\ge v 的数设为 11，一个区间 [l,r][l,r] 合法当且仅当 ∑i=lrai≥0\sum_{i=l}^{r} a_i \ge 0。
二分的检查函数返回中位数是否 ≤mid\le mid，检查时为了满足 r−l+1≥kr-l+1\ge k，从 r=kr=k 开始枚举，为了满足 prer−prel−1≥0pre_r-pre_{l-1} \ge 0，显然 prel−1pre_{l-1} 取到的是一段前缀最小值，最后记录答案就做完了。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...