【深基9.例4】求第 k 小的数 - 题解

P1923 【深基9.例4】求第 k 小的数（洛谷题面）

题目

题目描述：

输入 $n$（$1 \le n < 5000000$ 且 $n$ 为奇数）个数字 $a_i$（$1 \le a_i < {10}^9$），输出这些数字的第 $k$ 小的数。最小的数是第 $0$ 小。

请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。

输入格式：

第一行有两个整数，分别表示 $n$ 和 $k$。

第二行有 $n$ 个整数，第 $i$ 个数表示 $a_i$。

输出格式：

一个整数，表示第 $k$ 小的数。

数据范围与说明：

输入输出样例 #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;
}