求救，回复必关

FYR2013 @ 2025-01-05 20:04:37

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

by _xguagua_Firefly_ @ 2025-01-05 20:10:17

复杂度错了，你这个是 \Omicron(n ^ 2) 的，就是用排序也要用 \Omicron(\log n) 的，况且这个题会卡 \log 做法，得用分治的 \Omicron(n) 的做法。

并且数组空间开大点。

@FYR2013

by 4041nofoundGeoge @ 2025-01-05 20:14:15

@FYR2013直接快排，这样太慢了

by 4041nofoundGeoge @ 2025-01-05 20:14:54

快排是 O(n\log n)，冒泡是 O(n^2)。

by FYR2013 @ 2025-01-05 20:17:02

抱歉，我是个新手，看不太懂

by wangshengchen @ 2025-01-05 20:17:47

@FYR2013

还有一种方法，在main函数里加

ios::sync_with_stdio(false);
cin.tie(0);

再用正常的方法做，如：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[5000000+10];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    m=m+1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    cout<<a[m];
    return 0;
}

求关

by bsdsdb @ 2025-01-05 20:18:15

必关

by bsdsdb @ 2025-01-05 20:18:39

@FYR2013 你先把【模板】排序 做了

by zhusan @ 2025-01-11 00:08:48

1.cin>>arr[i]慢了，我上次好像用分治o(n)的时间复杂度，最后两个也超时了，用scanf("%d",arr[i])才没有超时。 2.这个排序太慢了，可能也会超时。可以先看一下其他的排序和sort函数。