这题真的难过！老坑了！

step 1: 题意理解

这题题目很短，意思就是在一个长度为 n 的数列中找到第 k 小数。

看上去很简单是吧，其实很难！我尝试了无数次还是 WA ！

那么这道题为什么这么难呢？

原因很简单，数据范围贼坑！

n 达到了惊人的10^7，这就意味着普通sort O(n log n) 时间复杂度根本不够！

而正解，花了我好几个月才想出来 doge 。。。。。。【令人头大.jpg】

step 2：问题建模与算法选择

思路 I ：sort 排序，排序整个数列，然后输出 a[k] 就可以了

错误代码示范 #1（声明：本次题解中所有的错误代码都是我亲自试过的）：

#include <bits/stdc++.h>
using namespace std;
int n, k, a[10000005];
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i]; 
    }
    sort(a+1, a+n+1);
    cout << a[k];
    return 0;
}

如果你也写出了这样的代码，那么

恭喜你，得到了一个大大的 0 分！TLE！

思路 II：快排（好像更快了），排序序列，输出 a[k]，简单直白

错误代码示范 #2：

#include <bits/stdc++.h>
using namespace std;
int a[10000005], n, k, x, m;
void quick_sort(int l, int r) {
    if (l >= r) {
        return;
    }
    int p1 = l, p2 = r;
    int pivot = a[l];
    while (p1 < p2) {
        while (a[p2] >= pivot && p1 < p2) {
            p2--;
        }
        while (a[p1] <= pivot && p1 < p2) {
            p1++;
        }
        if (p1 < p2) {
            swap(a[p1], a[p2]);
        }
    }
    swap(a[l], a[p1]);
    quick_sort(l, p1 - 1);
    quick_sort(p1 + 1, r);
}
int main() {
    cin >> n >> k;
    cin >> a[0] >> x >> m;
    for (int i = 1; i < n; i++) {
        a[i] = (long long)a[i - 1] * x % m;
    }
    quick_sort(0, n - 1);
    cout << a[k - 1] << endl;
    return 0;
}

如果你也写出了这样的代码，那么

恭喜你，得到了一个大大的 0 分！TLE！

为哈这两种方法都不行？

sort 的时间复杂度和普通快排是一样的，都是 O(n log n)

而对于题目中巨大的 n 我们需要一种 O(n) 及以下的时间复杂度才能AC qwq~ (´；ω；`)

所以，为了找到正解，我斥巨资，研究了一下这个题目：

∵ 两种经典的办法时间复杂度太高

又∵这两种办法都是对全数组进行排序

又∵我们只需要第 k 小的数

所以，

真相只有一个，

我们不需要对整个数组进行排序

比如说，当我们知道 a[k] 在左区间的时候，

右区间的情况就不重要了，

换就话说，

我们只需要不断的折半查找空间，也就是使用分治思想（将下标 i 折半到所需下标 k 所在的区间）

这样优化下的快排

时间复杂度可以降到O(n)

这样就可以——

A————C————！

step 3 最终章：代码实现！

核心改进的代码：

if (i > k) quicksort(l, i - 1); //左区间递归
if (i < k) quicksort(i + 1, r); //右区间递归

全部代码（请诸位观众大佬抄袭）：

#include <bits/stdc++.h>
using namespace std;
int a[10000005];
int n, k;
void quicksort(int l, int r){ //这个就是适用于这道题的快排啦，时间复杂度 O(n) 的
    if (l > r) return;
    int temp = a[l];
    int i = l, j = r;
    while (i != j){
        while (a[j] >= temp && i < j)
            j--;
        while (a[i] <= temp && i < j)
            i++;
        if (i < j)
            swap(a[i], a[j]);
    }
    swap(a[l], a[i]);
    //上面普通快排都有的

    if (i > k) quicksort(l, i - 1); //左区间递归
    if (i < k) quicksort(i + 1, r); //右区间递归
}
int main(){
    scanf("%d%d",&n,&k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    quicksort(1, n); //排序
    printf("%d\n", a[k]); //输出
    return 0;
}
//完结散花，完美AC！

本次的题解到此结束，

本菜鸡第一次写题解，

写得可能不太好，

请诸位大佬见谅，

顺便给个三连支持一下我这个寒酸的弱弱~

感谢大家的支持！

——————THE END！！！——————