本蒟蒻用sort TEL 60分

P1923 【深基9.例4】求第 k 小的数

HUC_fishfish @ 2024-10-11 20:47:56

-代码

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

by MLE_Automaton @ 2024-10-11 20:49:33

@HUC_fishfish 5e6你不t谁t，正解O(n)

by OIer_bcx_ @ 2024-10-11 20:50:03

O(NlogN)$ 过不了，要用$O(n)

by OIer_bcx_ @ 2024-10-11 20:50:29

@HUC_fishfish

by HUC_fishfish @ 2024-10-11 20:56:15

谢谢，换scanf、printf，ok了

by _chicken_ @ 2024-10-11 21:01:06

笑点解析：上面被打脸了，而且O(nlogn)的复杂度是正确的

by OIer_bcx_ @ 2024-10-11 21:04:49

@chicken 不是，正解本来就是O(N)

by _chicken_ @ 2024-10-11 21:05:41

@OIerbcx 自己用计算器算算吧，n*logn只有2e8左右，稳过的

|