为什么不能用sort啊，求大佬帮助

lisuhengyu0617 @ 2022-07-23 20:05:07

#include<bits/stdc++.h>
using namespace std;
int a[10000005];
int main(){
    int b,c;
    cin>>b>>c;
    for(int i=0;i<b;i++){
        cin>>a[i];
    }
    sort(a,a+b);
    cout<<a[c];
}

by yaotianhao @ 2022-07-23 20:11:56

你的数组下标要减一，因为你的数组下标是从0开始的。

by Super_Supper @ 2022-07-23 20:20:05

@lisuhengyu0617 因为 sort 是 O(n log n) 的，但是这题要 O(n)

by Pass1on_W @ 2022-07-23 20:28:11

观察数据，我们不难发现以下事情：

对于快排来说，它的时间复杂度为 O(nlog_2n) 的，将数据范围代入推算一下，会TLE 故我们需要寻求 O(n) 的算法解决这个问题

这个题不是说了要考虑分治算法吗

by 听取MLE声一片 @ 2022-07-23 20:43:16

@yaotianhao 不会就别乱说话

by naroanah @ 2022-07-23 20:56:02

因为 n \le 5 \times 10^6

by rxjdasiwzl @ 2022-07-24 00:10:10

@lisuhengyu0617 写快读开 O2 即可。

by rxjdasiwzl @ 2022-07-24 00:11:42

@sb_yyds @Pass1on_W @lifeTree 实测 433 ms，并不是「这题需要用 O(n) 的做法」。

by lisuhengyu0617 @ 2022-07-25 19:03:56

谢谢各位大佬的指教

by TheCliffSwallow @ 2022-07-29 21:22:51

@rxjdasiwzl 其实好像只要加速cin cout就能A（

by zhangjiahe__ @ 2022-08-04 20:49:17

用scanf,开O2