HDU 6231 Kth number(二分,双指针)
文章目录
题目描述
给定一个长度为 $n$ 的数组 $A$,给定 $m,k$,问在由这个数组的所有的区间第 $k$ 小组成的 $B$ 数组中,第 $m$ 大元素是多少
$1 \le n \le 10^5$
$1 \le A_i \le 10^9$
简要做法
设所有区间第 $k$ 小的第 $m$ 大元素为 $x$
由于 $m$ 和 $k$ 固定,$x$ 具有单调性,考虑二分 $x$ 计算区间个数是否大于等于 $m$
问题转化为是否有至少 $m$ 个区间有至少 $k$ 个元素大于等于 $x$
区间个数的计算使用双指针即可
枚举左端点,当找到一个右端点使得区间 $[l, r]$ 合法时,$[l, n]$ 也是合法的
复杂度 $O(nlog_2n)$
参考代码
#include <stdio.h>
#include <algorithm>
#include <memory.h>
#define int long long
const int N = 1e5 + 5;
int n, k, m, a[N];
int read()
{
int x = 0, f = 1;
char ch = getchar();
while ('0' > ch or ch > '9')
f = ch == '-' ? -1 : 1, ch = getchar();
while ('0' <= ch and ch <= '9')
x = x * 10 + ch - 48, ch = getchar();
return x * f;
}
bool judge(int mid)
{
int L = 1, R = 1, cnt = a[1] >= mid, res = 0;
while (R <= n)
if (cnt >= k)
res += n - R + 1, cnt -= a[L++] >= mid;
else
cnt += a[++R] >= mid;
return res >= m;
}
signed main()
{
for (int T = read(); T--;)
{
n = read(), k = read(), m = read();
for (int i = 1; i <= n; i++)
a[i] = read();
int res = -1;
for (int L = 1, R = 1e9, mid; L <= R;)
if (judge(mid = (L + R) >> 1))
res = mid, L = mid + 1;
else
R = mid - 1;
printf("%lld\n", res);
}
return 0;
}