第k小数

链接：https://ac.nowcoder.com/acm/contest/5773/A
来源：牛客网

时间限制：C/C++ 3秒，其他语言6秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
给你一个长度为n的序列，求序列中第k小数的多少。
输入描述:
多组输入，第一行读入一个整数T表示有T组数据。
每组数据占两行，第一行为两个整数n，k，表示数列长度和k。
第二行为n个用空格隔开的整数。
输出描述:
对于每组数据，输出它的第k小数是多少。
每组数据之间用空格隔开
示例1
输入
复制
2
5 2
1 4 2 3 4
3 3
3 2 1
输出
复制
2
3
备注:
t \leq10 , 1\leq n\leq5\times 10^6,k\leq n,数列里每个数都在int范围内t≤10,1≤n≤5×10
6
,k≤n,数列里每个数都在int范围内
由于输入比较多，请使用快读读取。
例如：
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;
}

题解：
这道题就比较水了，直接是上课讲过的原题，sort半排序即可。但数据规模改的让我直接白白wa了5发。。。。。QAQ
写出快排函数然后最后加if判断下一次排那一部分就好，不过要注意边界情况，到边界就输出，没到过就最后输出，不然可能段溢出。。。。复杂度logn

思维就更简单了，就是只需要第k小数，那么排完一遍后就知道基准是第几小数，所以另一半就无需再管了。

另：四个月前做过一道题，就差求第k大数，结果我只想到选择排序，直接复杂度爆表，下次长记性了。。。。QAQ

代码：
using namespace std;
#include <bits/stdc++.h>
#define int long long
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[5000005];int n;int k;
int flag=0;
void solve(int start, int last)
{
int i=start;
int j=last;
int temp=a[i];
if (i<j)
{
while (i<j)
{
while (i<j&&a[j]>=temp )
j--;
if (i<j)
{
a[i]=a[j];
i++;
}
while (i<j&&temp>a[i])
i++;
if (i<j)
{
a[j]=a[i];
j--;
}
}
//把基准数放到i位置
a[i] = temp;
if (i==k-1)
{
cout<<a[i]<<'\n';
flag=1;
return ;
}
if (i>k-1)//只要排序一半就好
solve(start,i-1);
else
solve(i+1,last);
}
}
signed main (void)
{
int t;t=read();
while (t--)
{
n=read();k=read();
memset (a,0,sizeof a);
for (int i=0;i<n;i++)
{
a[i]=read();
}
solve(0,n-1);
if (flag==0)
cout<<a[k-1]<<'\n';
}
return 0;
}