咋莫名其妙超时了？

han_bai @ 2023-05-25 20:48:00

#include <bits/stdc++.h>
using namespace std;
long long a[5000005];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n);
    cout << a[k];

    return 0;
}

by han_bai @ 2023-05-25 20:53:09

自己后来试了下printf和scanf加上O2 然后就通过了

by xiaoyang111 @ 2023-05-25 20:53:43

本题考的是分治，也就是快排，但sort的时间复杂度好像是{O(n*logn)},而快排快一些(虽然我没做，但我好像知道知道为什么)

by LiJoQiao @ 2023-05-25 20:53:52

O(nlogn)复杂度过不了,需用二分方法

by xiaoyang111 @ 2023-05-25 20:55:06

printf和scanf快一点

by LiJoQiao @ 2023-05-25 20:55:59

@xiaoyang111 并不是快排快一些,sort函数是堆排快排插排等综合成的,按情况选择快速的排序方法,之所以会超时是因为本题正解是在快排的思想基础上,舍弃k不在的区间来优化算法

by xiaoyang111 @ 2023-05-25 20:59:20

@LiJoQiao 知道了