二分 k-th number

K-th Number

题目链接

题目大意

给一个数组a包含n（1e5）个数，给出 k，m。
构造数组b：在a的所有大于等于k的区间中选出第k大的数加到b里面。
问b数组中第m大的数。

题解

我好菜。。想不到二分，感觉最近脑子不动了，很fan
二分答案，
然后怎么check？
b里的数肯定有m个大于等于mid的数。
怎么看有没有呢？ 可以用m当作check的条件改变二分的l，r。
统计区间里第k大大于等于mid的数量，怎么统计？尺取，
就相当于取k个大于等于mid的数 有多少个区间，
尺取可以枚举区间的左侧，然后尺取 取到右侧，然后统计就可以，，

代码

 #include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
#include <cmath>
#include <set>
#include <queue>
#include <string>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
int a[maxn];
int n,k;
ll m;
bool pd(int x)
{
   
	ll s =0 ;
	int sum = 0, l= 1, r = 1;
	while(1)
	{
   
		while(r <= n && sum < k)
		{
   
			if(a[r] >= x)
				sum ++ ;
			r ++ ;
		}
		if(sum < k)
			break;
		s += n - r + 2;
		if(a[l] >= x) sum -- ;
		l ++ ;
	}
	return s >= m;
}


int main()
{
   
	int T;
	scanf("%d",&T);
	while(T -- )
	{
   
		
		scanf("%d%d%lld",&n,&k,&m);
		for (int i = 1; i <= n; i ++ )
			scanf("%d",&a[i]);
		int l = 0,r = 1e9;
		while(l < r)
		{
   
			int mid = l + r + 1 >> 1;
			if(pd(mid))
				l = mid;
			else
				r = mid - 1;
		}
		printf("%d\n",l);

	}
}

我菜了。。