居然是二分,真的是没想到。。。
题目大意:
给n个数字ai,从这n个数中取任意长度不小于k的区间,对每个区间都获得其中的第k大的数。将这些区间中获得的第k大的数都放入数组b中,问数组b中的第m大的数字是多少?
n<=100000,0<=ai<=10^9
思路:
枚举区间肯定不行。
这里考虑二分答案。
假设二分当前答案为x,那么我们如果我们可以找到超过m-1个区间,其中这些区间中的第k大数字大于x,就说明当前二分的答案太小了。
二分策略是成立的。
那么如何查找到底有多少个满足条件的区间呢?
这里用尺取法,我们维护两个指针l,r,一开始l=r=1,接着我们往右移动r,同时统计大于x的数字个数t,当数字个数t=k的时候,我们得到了第一个满足条件的区间[l,r],显然r往后的区间都满足,所以我们可以得到l=1时满足条件的区间个数为n-r+1。
接着我们往右移动l,此时l=2,然后我们根据t=k,看r是否需要往右移动,如果需要移动则移动到t=k为止。那么又可以得到满足条件的区间个数n-r'+1
此时我们的方法出来了,枚举l,然后移动r计算满足条件的区间。
由于r只往右移动,因此复杂度为O(n)。
假设二分,总复杂度为O(nlogn)
代码:
#include<bits/stdc++.h> using namespace std; int n,k,a[100040]; long long m; bool check(int x){ int t=0; long long cnt=0; for(int l=1,r=1;l<=n;l++){ while(t<k&&r<=n){ if(r<=n&&a[r++]>x)t++; } // cout<<l<<'*'<<r<<endl; if(t<k)return false; cnt+=(n-r+2); if(cnt>m-1)return true; if(a[l]>x)t--; } return false; } int main() { int T; cin>>T; while(T--){ cin>>n>>k>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } int l,r; l=1; r=1000000001; while(l<r){ int mid=l+r>>1; if(check(mid))l=mid+1; else r=mid; //cout<<l<<' '<<r<<endl; } cout<<r<<endl; } return 0; }