problem

题意搞了很久才搞懂233.
给出一个序列,对于每个长度的子段,会将其中第大的元素放进集合中。最后询问集合中第大的子段。

solution

首先二分一个答案。然后一下区间第大大于等于的区间个数,如果,那么说明还可以再放大并且可以成为答案,否则说明需要缩小。

然后考虑函数如何写。维护两个指针。然后向右不断的挪动。当区间内大于等于的数字个数个时,说明当前区间是一个合法区间,此时在满足区间的个数的条件下,再不断的向右挪动。对于此时经过的每个,以他们为左端点,并且以中的任意一个数为右端点时,都是一个合法区间。

code

/*
* @Author: wxyww
* @Date:   2020-04-21 18:38:06
* @Last Modified time: 2020-04-21 18:59:09
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 100010;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
ll a[N],n,m,K;
bool check(int x) {
    int now = 0,p = 1;ll ret = 0;
    for(int i = 1;i <= n;++i) {
        if(a[i] >= x) ++now;
        while(now >= K) {
            now -= (a[p++] >= x);
            ret += (n - i + 1);
        }
    }
    return ret >= m;
}
int main() {
    int T = read();
    while(T--) {
        n = read(),K = read(),m = read();
        for(int i = 1;i <= n;++i) a[i] = read();

        int l = 1,r = 1000000000,ans = 0;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(check(mid)) ans = mid,l = mid + 1;
            else r = mid - 1;
        }
        cout<<ans<<endl;
    }
    return 0;
}