【HDU - 6231】K-th Number（二分，思维）

题干：

Alice are given an array A[1..N]A[1..N] with NN numbers. 

Now Alice want to build an array BB by a parameter KK as following rules: 

Initially, the array B is empty. Consider each interval in array A. If the length of this interval is less than KK, then ignore this interval. Otherwise, find the KK-th largest number in this interval and add this number into array BB. 

In fact Alice doesn't care each element in the array B. She only wants to know the MM-th largest element in the array BB. Please help her to find this number.

Input

The first line is the number of test cases. 

For each test case, the first line contains three positive numbers N(1≤N≤105),K(1≤K≤N),MN(1≤N≤105),K(1≤K≤N),M. The second line contains NN numbers Ai(1≤Ai≤109)Ai(1≤Ai≤109). 

It's guaranteed that M is not greater than the length of the array B. 

Output

For each test case, output a single line containing the MM-th largest element in the array BB.

Sample Input

2 5 3 2 2 3 1 5 4 3 3 1 5 8 2

Sample Output

3 2

题目大意：

有一个长度为N的序列A={a1,a2,a3.....aN},该序列有多个子区间,考虑所有长度大于等于K的区间,我们找出所有这些区间的第K大值b,这些b又组成了一个序列B,现在你需要求出序列B的的第M大值。

解题报告：

首先我们知道如果这个数是x的话，那>x的数都可以看成x，二分这个数之后，在check函数中看有多少个区间满足第K大的数是>=x的，我们如果把>=x的数都标记成1的话，也就是看有多少区间的1的个数是>=k的，这一点可以尺取完成。如果区间数>=M的话，说明需要调整左端点，同时需要记录答案。

AC代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; int a[MAX],b[MAX]; int qq[MAX],sum[MAX]; int n,k; ll M; int ok(int x) {ll sum = 0;for(int i = 1; i<=n; i++) qq[i] = a[i] >= x;int l = 1,r = 1,tmp = 0;while(l<=r && r<=n) {tmp += qq[r];while(tmp >= k && l<=r) {tmp -= qq[l];l++;}sum += l-1;r++;} // sum--;return sum>=M; } int main() {int t;cin>>t;while(t--) {scanf("%d%d%lld",&n,&k,&M);for(int i = 1; i<=n; i++) scanf("%d",a+i),b[i] = a[i]; // int l = 0,r = *max_elememt(a+1,a+n+1); 这样不行 太大了。sort(b+1,b+n+1);int l=1,r=n,m,ans;while(l<=r) {int mid=(l+r)>>1;if(ok(b[mid])) l = mid+1,ans=mid;//else r = mid-1;}printf("%d\n",b[ans]); }return 0 ; }

 

总结

以上是生活随笔为你收集整理的【HDU - 6231】K-th Number（二分，思维）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。