最后两个TLE，求助

Guan_qiqi @ 2020-05-07 23:23:54

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    long long buf[n];
    for(int i=0; i<n; i++){
        cin >> buf[i];
    }

    sort(buf, buf+n);

    cout << buf[m];

    return 0;
}

by Implicit @ 2020-05-07 23:26:27

@Guan_qiqi 这个题要用分治做的，暴力过不了

by Implicit @ 2020-05-07 23:28:29

具体思路是首先枚举中间点 mid，然后将序列 a 中 <mid 的排在 mid 左边，>mid 的排在 mid 右边。

然后将左右数字数量与 k 比较，确定下一个区间继续递归。

最后就能取得。

最好复杂度每次都取平均数，\mathcal O(\log n)；最坏每次都是边界 \mathcal O(n)。

@Guan_qiqi

by 清清老大 @ 2020-05-07 23:42:20

@Guan_qiqi 快读加sort

by Guan_qiqi @ 2020-05-07 23:45:28

@LoveMC 谢谢，sort的复杂度O(nlogn)已经很低了，我改改输入试试

by Guan_qiqi @ 2020-05-08 00:03:13

@清清老大 还是60分，最后两个TLE

#include<bits/stdc++.h>

using namespace std;

int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    int buf[n];
    for(int i=0; i<n; i++){
        buf[i] = read();
    }

    sort(buf, buf+n);

    printf("%d", buf[m]);

    return 0;
}

by TKater_yzt @ 2020-05-08 07:02:36

@Guan_qiqi 这题用sort卡不过去的

by Implicit @ 2020-05-08 15:44:10

谢谢，sort 的复杂度 \mathcal O(n\log n) 已经很低了，我改改输入试试

@Guan_qiqi n<5000000，n\log n<5000000\times\log 5000000\approx 5000000\times 15=75000000，宁的计算机 1s 能跑 75000000 个数据？

by Lucifero @ 2020-05-08 22:10:32

我也有同样的问题……

by Guan_qiqi @ 2020-05-09 19:43:30

@LoveMC 感谢感谢，现在看懂了！！

by Guan_qiqi @ 2020-05-09 20:14:42

@GWKOD 试试STL的nth_element()这个函数

输入输出不要用cin、cout，最后两个会TLE 用scanf，printf过了

附上代码：

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n, k;
    scanf("%d%d", &n, &k);
    int a[n];
    for(int i=0; i<n; i++){
        scanf("%d", &a[i]);
    }

    nth_element(a, a+k, a+n);

    printf("%d", a[k]);

    return 0;
}