题解 | #第k小数#

来源：牛客网

题号：NC207028
时间限制：C/C++ 3秒，其他语言6秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述 
给你一个长度为n的序列，求序列中第k小数的多少。
输入描述:
多组输入，第一行读入一个整数T表示有T组数据。
每组数据占两行，第一行为两个整数n，k，表示数列长度和k。
第二行为n个用空格隔开的整数。
输出描述:
对于每组数据，输出它的第k小数是多少。
每组数据之间用空格隔开

#include<bits/stdc++.h>
using namespace std;
//这题的主要算法是递归思想的一个应用：归并排序，然后归并排序的最大特点是每次只排对应于随机取定的那个mid值大小两边的元素，且两边元素的排序情况未知待定，所以我们利用这一特点进行查找，将最后两个端点指针真正趋向的下标与我们所要求的第k小数的k作大小比较，之后继续进行递归操作，来最后趋近于所要求的值
inline int read(){//这里是快速读取函数
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
int a[5001000];
int kpaixu(int i , int j ,int k){
    int l = i , r = j;
    if (l == r){//这种情况的意思是上一次满足循环条件后其中一个端点和k值相等，而恰好另一个端点也是k值，所以该点就是所要求的点
    //这句话很关键！！！因为符合条件直接输出值的大致有两种情况，一种是刚好两个端点之间夹着一个k值，也就是程序最下面的else情况，另一种就是K值正好卡在一个端点处，那么下一次循环时就直接输出值了，也就是这种情况，而无这种情况返回值的话通过样例就是0（我也不知道为什么！）
        return a[l];
    }
    int mid = (l + r) / 2;
    int x = a[mid];
    while (l < r){
        while (a[l] < x) l ++ ;
        while (a[r] > x) r -- ;
        int p = a[l]; a[l] = a[r]; a[r] = p;
        l ++ ; r -- ;
    }
    if (r >= k - 1) return kpaixu(i , r , k);
    else if (l <= k - 1) return kpaixu(l , j , k);
    else return x;
}
int main(){
    int t;
    cin >> t;
    int n, k ;
    for (int i = 0 ; i < t; i ++ ){
            cin >> n >> k;
            for (int j = 0; j < n ; j ++ ){
                a[j] = read();
            }
            cout << kpaixu(0, n - 1, k) << endl;
    }
    return 0;
}