RE求助！

shiguangsijian @ 2024-08-29 09:49:19

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

by ikunTLE @ 2024-08-29 09:51:28

@shiguangsijian 1\le n<5000000

by hhhh2971 @ 2024-08-29 09:52:51

一会就变成TLE求助了

by HuangSiHan3116 @ 2024-08-29 10:01:11

@shiguangsijian 这个包废的。 函数

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

能帮你排序

by HuangSiHan3116 @ 2024-08-29 10:02:37

还有，你要用

scanf("");

输入

by HuangSiHan3116 @ 2024-08-29 10:03:18

求关 @shiguangsijian

by shiguangsijian @ 2024-08-29 10:06:15

@HuangSiHan3116 请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。

by shiguangsijian @ 2024-08-29 10:06:41

@shiguangsijian 题目说的

by HuangSiHan3116 @ 2024-08-29 10:08:15

尽量不要使用

by HuangSiHan3116 @ 2024-08-29 10:11:11

@shiguangsijian 又不是不给用。

by hhhh2971 @ 2024-08-29 14:24:32

@shiguangsijian 用二分，你可以看看我的代码：

#include<bits/stdc++.h>
using namespace std;

int a[5000005];
int n,k;

int quick(int l,int r,int k)
{
    int mid;
    int s=rand()%(r-l+1)+l;
    swap(a[l],a[s]);
    int ll=l,rr=r;
    while (ll<rr)
    {
        while (a[rr]>=a[l] && ll<rr)
            rr--;
        while (a[ll]<=a[l] && ll<rr)
            ll++;
        if (ll<rr) swap(a[ll],a[rr]);
    }
    swap(a[l],a[ll]);
    mid=ll;
    if (k==mid) return a[k];
    if (k>mid) return quick(mid+1,r,k);
    if (k<mid) return quick(l,mid,k);
}

int main()
{
    srand(time(0));
    cin >> n >> k;
    k++;
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    cout << quick(1,n,k) << endl;

    return 0;
}