思路

题意:将length >= k 的区间中的第k大的数放入b[i]中, 求b[i]中第m大的数

暴力枚举o(n^2):TLE
二分o(nlogn) + 尺取:[0, 10^9]区间找x, 使 >= x 的区间有k大的数, 且满足数的个数 >= m <==> lim (x -> ans) 使得区间数 -> m

拓展

1. 整数二分两个模板

#include <iostream>
#include <cstring>
#include <algorithm>

#define LL long long

using namespace std;

const int N = 1e5 + 10;

int t, n, k;
LL m;
int a[N];

bool check(int x)
{
    int num = 0;
    LL res = 0;
    for(int i = 1, j = 1; i <= n; i ++ )
    {
        if(a[i] >= x) num ++ ;
        if(num == k)
        {
            res += n - i + 1;
            while(a[j] < x) 
            {
                res += n - i + 1;
                j ++ ;
            }
            num -- ;
            j ++ ;
        }
    }
    return res >= m;
}

int main()
{
    cin >> t;
    while(t -- )
    {
        cin >> n >> k >> m;
        for(int i = 1; i <= n; i ++ ) cin >> a[i];
        int l = 0, r = 1e9;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(check(mid)) l = mid;
            else r = mid - 1;
        }
        cout << l << endl;
    }
    return 0;
}