题目描述：
输入 （$1 \le n < 5000000$ 且 为奇数）个数字 （$1 \le a_i < {10}^9$），输出这些数字的第 小的数。最小的数是第 小。
请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。
输入格式：
第一行有两个整数，分别表示 和 。
第二行有 个整数，第 个数表示 。
输出格式：
一个整数，表示第 小的数。
数据范围与说明：
输入输出样例 #1
输入：
5 1
4 3 2 1 5
输出：
2
评论已关闭
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PLL;
int a[5000005];
int n,k;
void qsort(int i,int j){
int l=i,r=j,mid=a[(l+r)/2];
while(l<=r){
while(a[r]>mid){
r--;
}
while(a[l]<mid){
l++;
}
if(l<=r){
swap(a[l],a[r]);
r--;
l++;
}
}
if(k<=r){
qsort(i,l);
}else if(l<=k){
qsort(r,j);
}else{
cout<<a[r+1];
return ;
}
}
void solve() {
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>a[i];
}
qsort(0,n-1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while (t--) {
solve();
}
return 0;
}