80分求助 第四个数据MLE了

L409582940 @ 2021-05-28 20:29:57

int quick_sort(int q[], int l, int r)
{
if (l >= r) return q[l];

int i = l - 1,j = r + 1,x=q[l + r >> 1];
while (i < j)
{
    do i ++ ; while (q[i] < x);
    do j -- ; while (q[j] > x);
    if (i < j) swap(q[i], q[j]);
}

if(k<=j) quick_sort(q,l,j);
else if(i<=k) quick_sort(q,i,r);
}

by zhangruozhong @ 2021-05-28 20:35:13

可以直接用nth_element(a,a+k,a+n)函数 不需要快排

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

by JJA_ @ 2021-05-28 20:54:20

@zhangruozhong

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

别人想练习快排恁在这里干什么呢？？

@L409582940 您可以发一下所有的代码吗？可能是一些奇怪的问题

by zhangruozhong @ 2021-05-28 20:57:47

@L409582940 我建议试一下二分

int quicksort(int left,int right)
{
    int mid=a[left];
    while (left<right) 
    {
        while (left<right&&mid<=a[right])
            right--;
        a[left] = a[right];
        while (left<right&&a[left]<=mid)
            left++;
        a[right] = a[left];
    }
    a[left]=mid;
    return left;
}

by zhangruozhong @ 2021-05-28 20:58:38

#include<bits/stdc++.h>
using namespace std;
long long a[5000010];
inline int read(){
    char ch=getchar();
    int x=0,f=1;
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    } 
    while('0'<=ch&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    } return x*f;
}
int quicksort(int left,int right)
{
    int mid=a[left];
    while (left<right) 
    {
        while (left<right&&mid<=a[right])
            right--;
        a[left] = a[right];
        while (left<right&&a[left]<=mid)
            left++;
        a[right] = a[left];
    }
    a[left]=mid;
    return left;
}
int find(int left, int right, int k)
{   
    int tem=quicksort(left,right);
    if(k==tem)
        printf("%d",a[k]);
    else if(k-1<tem)
        find(left,tem-1,k);
    else
        find(tem+1,right,k);
    return 0;
}
int main()
{
    int n,k;
    n=read();
    k=read();
    for(int i=0;i<n;i++)
        a[i]=read();
    find(0,n-1,k);
    return 0;
}

by L409582940 @ 2021-05-28 21:57:15

@蒟蒻JJＡ 很奇怪 麻烦大佬

#include <iostream>

using namespace std;

const int N = 5000010;

int q[N];
int n, k;
int quick_sort(int q[], int l, int r)
{
    if (l >= r) return q[l];

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }

    if(k<=j) quick_sort(q,l,j);
    else if(i<=k) quick_sort(q,i,r);
    else return q[j+1];
}

int main()
{

    scanf("%d%d", &n, &k);

    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    cout << quick_sort(q, 0, n - 1) << endl;

    return 0;
}

by L409582940 @ 2021-05-28 21:57:32

@zhangruozhong 谢谢

by zhangruozhong @ 2021-05-29 10:58:38

你这个代码应该是内存超限了

by zhangruozhong @ 2021-05-29 10:59:13

应该没错

by L409582940 @ 2021-05-30 12:58:44

@zhangruozhong 谢谢