快排求助，WA #4

little_q_exist @ 2024-10-19 15:43:26

#include<cstdio>
using namespace std;
long long a[5000010],t;
void part(long long l,long long r,long long k){
    long long i = l,j = r,flag = a[(l+r)/2];

    while (i<j)
    {
        while (i<j && a[j] >= flag) j--;
        while (i<j && a[i] <= flag) i++;
        t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    t = flag;
    a[(l+r)/2] = a[i];
    a[i] = t;

    if (k > i) part(i+1,r,k);
    if (k < i) part(l,i-1,k);
    if (k == i)
    {
        printf("%lld",a[i]);
        return ;
    }
}
int main(){
    long long n,k;
    scanf("%lld %lld",&n,&k);
    for (long long i = 1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    part(1,n,k);
    return 0;
}

by sgy_always_ac @ 2024-10-19 15:54:02

#include<bits/stdc++.h>
using namespace std;
int a[5000005];
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    cout<<a[k+1];
    return 0;
}

直接快排不香吗

by YuYuanPQ @ 2024-10-19 15:54:11

能下数据吗

by 玉树临风英俊潇洒 @ 2024-10-19 15:54:50

@little_q_exist

快排是 O（nlogn)过不了此题（求关

STL是个好东西少走不少弯路（求关

#include<bits/stdc++.h>
using namespace std;
int x[5000005],k;
int main()
{
    int n;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
        scanf("%d",&x[i]);
    nth_element(x,x+k,x+n);
    printf("%d",x[k]);
}

（求关

by YuYuanPQ @ 2024-10-19 15:54:53

@little_q_exist 给个数据方便点。

by YuYuanPQ @ 2024-10-19 15:55:48

@玉树临风英俊潇洒 可以的。

by little_q_exist @ 2024-10-19 15:58:26

@YuYuanPQ 下不了数据（捂脸

by little_q_exist @ 2024-10-19 16:00:29

@shenguoyuan0901 @YuYuanPQ @玉树临风英俊潇洒 已关，stl大法好

by Max_robot @ 2024-10-19 16:02:12

@little_q_exist 可以用归并排序

by YuYuanPQ @ 2024-10-19 16:02:43

@little_q_exist 好吧