算法入门课2-总结

K -th Number
链接:https://ac.nowcoder.com/acm/problem/14301
题目大意
给定数组A，将数组A中第k大的数加入数组B中，输出数组b中的第m大的数
易错点
本题没有给m的数据范围，由于数组A的大小为n，可以组成的区间大小为（n - 1） * n / 2
代码如下：
n为1e5，故m超出了int的范围要用long long

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;

int n, k, a[N];
ll m;
/*
    如果一个区间中有k个数>=x 说明res >= x
    如果这样的区间的总个数>=m 说明res <= x 
*/
bool check(int x) { //
    ll tot = 0;  //区间第k大的数大于x的区间有多少个
    for(int l = 1, r = 0, sum = 0; l <= n; l++) {  //快慢指针，快指针一开始要小于满指针
        while(r + 1 <= n && sum < k) {
            sum += a[++r] >= x; 
        }
        if(sum == k) tot += n - r + 1;  //从r到 n 大于等于x的数都成立
        sum -= a[l] >= x; //
    }
    return tot >= 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 = 1, r = 1000000000;
                /*
                    由于a[i]的范围为1 - 1e9
                    故 l = 1， r = 1e9
                */
        while(l < r) {
            int mid = (1 + l + r) >> 1;
            if(check(mid)) l = mid;  
            else r = mid - 1;
        }
        printf("%d\n", l);
    }
    return 0;
}