大佬求助，后两个超时。。。

jh2023 @ 2023-08-11 15:48:48

#include <bits/stdc++.h>
using namespace std;
long long a[5000050];
bool cmp(int a, int b) {
    return a < b;
}
int main() {
    /*std::ios::sync_with_stdio(false);*/
    long long n, k;
    cin >> n >> k;
    /*scanf("%d %d", &n, &k);*/
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    k += 1;
    sort(a + 1, a + n + 1, cmp);
    int result = a[k];
    cout << result;
    return 0;
}

by Zz__Cc @ 2023-08-11 15:59:40

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

by Zz__Cc @ 2023-08-11 16:00:22

@jh2023 快排本来就只有60

by yezicong1104 @ 2023-08-14 10:48:40

把cin改成scanf的写法,scanf比cin效率高

by harespeed @ 2023-08-16 11:17:38

@Zz__Cc 归并也是60(恼)

by Zz__Cc @ 2023-08-16 13:08:03

@harespeed 可以用二分思想套

by harespeed @ 2023-08-16 14:30:19

@Zz__Cc 二分的话，也需要在序列是有序情况下实现，这样貌似更耗时呢。求第k小的数如果是以顺序结构存储的话，还可以直接存取，比二分貌似要好吧。

by Zz__Cc @ 2023-08-16 20:00:16

@harespeed 并不是纯粹的二分，是要通过二分思想优化，比如把它“切开”然后分层次去搜索

by Chun_My @ 2023-08-18 10:37:13

@jh2023 不如在sort的基础上开启O2优化（狗头