K-th Number
一、题意描述
对数列A的每个区间求第K大,并将第K大插入到B中,再求B中的第M大。
输入描述: The first line is the number of test cases.For each test case,the first line contains three positive numbers N(1 ≤ N ≤ 10^5);K(1 ≤ K ≤ N);M.
The second line contains N numbers Ai(1 ≤ Ai ≤ 10^9).
It's guaranteed that M is not greater than the length of the array B.
输出描述:
For each test case,output a single line containing the M-th largest element in the array B.
二、题意分析
首先先理解该题意,题目的意思其实是从A中的某一区间取出在该区间中第K大的数,并将其插入到B中,当A中长度不足K时,此时就不再插入,求B中第M大的元素.先说说我对这道题的思考吧,其实刚开始我自己写这道题的时候,可能是由于还没太理解这道题的题意吧,就导致刚开始雨巨讲这道题的时候没太理解,但是后来随着自己不断重现雨巨的思路,其实慢慢地就逐渐理解了这道题,可能这就是“由果溯因”吧.
对于这道题,肯定暴力枚举这个方法咱们都能想到,但是这肯定会卡我们的时间复杂度,那么我们就得换一个思路.咱们再仔细分析该题,发现其答案具有单调性,当我们二分出来的答案 <= 真实答案,此时说明咱们可以继续往大了二分,即l = mid - 1;而当我们二分出来的答案 > 真实答案时,此时说明我们需要往小了二分,即r = mid - 1;那么二分验证的思路又是什么呢?
首先我们思考我们二分的答案是序列B中的第M大,而这个数又是拿出部分数后的序列A中的第K大数,那么其实想到这里思路其实已经出来了.我们需要从A中拿出M个数,而这M个数中每次从区间取出来的时候都是其区间的第K大,那么其实该验证思路已经转换成A中第K大数大于等于x的区间总数要大于等于M个.再想明白这点之后,其实后续也就简单了,后续我们只需要该区间个数是多少就行了,也就需要注意一下尺取法的一个易错点.我们枚举区间的左端点L,然后去枚举右端点R.根据题意的特点,可以采取尺取进行优化.
时间复杂的分析:二分的时间复杂度为O(logn),而验证的时间复杂度是O(n),所以综上该程序总的时间复杂度为O(nlogn).
三、代码分析
当上面思路想清楚以后,其实AC代码就呼之欲出了,AC代码如下:
using namespace std;
typedef long long ll; //注意不要超出数据范围
int t,n,k,a[100010];
ll m;
bool judge(int x){
ll cnt = 0,ans = 0;
int l = 1,r = 1;
for (;l <= n;l++){
if (a[l - 1] >= x) cnt--;
for (;r <= n;r++){
if (a[r] >= x) cnt++;
if (cnt >= k){
ans += (n - r + 1);
if (a[r] >= x) cnt--; //此时要注意,进入该条判断语句后,break掉之后r不会继续++,下次循环有可能会使得cnt重复++
break;
}
}
}
return ans >= m;
}
int main(){
scanf("%d",&t);
while (t--){
scanf("%d%d%lld",&n,&k,&m);
int l = 1,r = 0;
for (int i = 1;i <= n;i++){
scanf("%d",&a[i]);
r = max(r,a[i]);
}
while (l <= r){
int mid = (l + r) >> 1;
if (judge(mid)) l = mid + 1;
else r = mid - 1;
}
cout << l - 1 << endl;
}
return 0;
}
四、个人总结
其实以后主要还是要先理解题意,得把题意理解清楚,如此方能进行下一步的求解.总的来说,该题其实是一个比较好的二分、分治的题.也需要我不断回顾该题.
