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; }