脚本宝典收集整理的这篇文章主要介绍了补题*总结题21/9/18，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

#include <bITs/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10;
int n,k,a[100009],m;
bool isok(int x)
{
    int ans=0,num=0,j=1;
    /*
    *ans：多少个区间的第k大比mid还大  and 右端点
    *num：统计有多少个数大于当前x
    *j：左端点
    */
    for(int i=1; i<=n; i++)//遍历A数组
    {
        if( a[i]>=x )
        {
            num++;//更新num
        }

        if( num==k )//说明包含当前区间的区间的第k大一定大于等于mid
        {
            ans+=(n-i)+1;//在 i+1 及其之后的区间大于x的点的个数都大于等于k个。
            //右端点的取值
            while( a[j]<x )//移动左端点
                /*
                *如果左端点小于x，则对第k大无影响
                */
            {
                ans+=n-i+1; //在 i+1 及其之后的区间大于x的点的个数都大于等于k个。
                j++;
            }
            num--;
            j++;
        }
    }
    if(ans>=m)	return true;//如果当前x符合题意
    else      return false;
}
signed main()
{
    int t;
    cin >> t;
    while( t-- )
    {
        cin >>n>>k>>;m;
        int l=1e9+1,r=0;
        for(int i=1; i<=n; i++)
        {
            cin >> a[i];
            l = min(l,a[i]);
            r = max(r,a[i]);
        }
        int ans=0;
        while( r>=l )
        {
            int mid =(l+r)/2;
            //  cout <<mid <<endl;
            if( isok(mid) )//如果当前x符合题意
            {
                l=mid+1;//二分缩短区间
                ans=mid;
            }
            else
            {
                r=mid-1;//二分缩短区间
            }
        }
        cout << ans <<endl;
    }
}

脚本宝典总结

以上是脚本宝典为你收集整理的补题*总结题21/9/18全部内容，希望文章能够帮你解决补题*总结题21/9/18所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。