HDU 6231. 二分+ 尺取
原题链接
简单
作者:
史一帆
,
2021-04-28 22:01:18
,
所有人可见
,
阅读 203
#include <iostream>
#include <cstring>
#include <algorithm>
typedef long long LL;
using namespace std;
const int N = 100010;
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;
}