K-th Number
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 599 Accepted Submission(s): 234
Now Alice want to build an array B by a parameter K as following rules:
Initially, the array B is empty. Consider each interval in array A. If the length of this interval is less than K, then ignore this interval. Otherwise, find the K-th largest number in this interval and add this number into array B.
In fact Alice doesn't care each element in the array B. She only wants to know the M-th largest element in the array B. Please help her to find this number.
For each test case, the first line contains three positive numbers N(1≤N≤105),K(1≤K≤N),M. The second line contains N numbers Ai(1≤Ai≤109).
It's guaranteed that M is not greater than the length of the array B.
//m要用long long 啊。
//二分答案x,然后尺取。找到有多少个区间存在至少k个大于等于x的数,如果这样的区间数不少于m个就说明第m大的数
//比x大,因此有单调性。尺取区间[l,r]中有k个不小于x的数那么会有n-r+1个符合的区间。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int MAXN=;
int n,k,a[MAXN];
ll m;
bool solve(int x)
{
ll sum=;
int tmp=,l=,r=;
while(){
while(tmp<k){
++r;
if(r>n) break;
if(a[r]>=x) tmp++;
}
if(r>n) break;
sum+=(n-r+);
if(a[l]>=x) tmp--;
l++;
}
if(sum>=m) return ;
return ;
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d%lld",&n,&k,&m);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
int l=,r=1e9,ans=;
while(l<=r){
int mid=(l+r)>>;
if(solve(mid)) { ans=mid;l=mid+; }
else r=mid-;
}
printf("%d\n",ans);
}
return ;
}