1 条题解

  • 0
    @ 2023-5-2 22:36:02
    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int N=1e6+10;
    int n,m,k,ans,a[N],b[N];
    bool check(int x){
    	int cnt=0,rk=0,t=0,i;
    	for(i=1;i<=n;i++){
    		while(t<=n&&cnt<m) if(a[++t]>=x) ++cnt;
    		if(cnt>=m) rk+=n-t+1;
    		cnt-=(a[i]>=x);
    	}
    	return rk>=k;
    }
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	cin>>n>>m>>k;
    	for(int i=1;i<=n;i++){
    		cin>>a[i];
    		b[i]=a[i];
    	}
    	sort(b+1,b+1+n);
    	int l=1,r=n;
    	k=((n-m+1)*(n-m+2)>>1)-k+1;
    	while(l<=r){
    		int mid=(l+r)>>1;
    		if(check(b[mid])) ans=b[mid],l=mid+1;
    		else r=mid-1;
    	}
    	cout<<ans;
        return 0;
    }
    
    
    • 1

    信息

    ID
    2940
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    260
    已通过
    8
    上传者