请问怎么解决运行超时呢

bennini_217 @ 2024-12-27 09:43:12

//快速排序找第k小
#include<bits/stdc++.h>
using namespace std;

int partition(vector<int>& p,int l,int r){
    int i=l;
    int j=r-1;
    int t=p[r];
    while(1){
        while(p[i]<t){
            i++;
        }
        while(p[j]>t&&j>l){
            j--;
        }
        if(i>=j){
            break;
        }
        swap(p[i],p[j]);
        i++;
        j--;
    }
    swap(p[i],p[r]);
    return i;
}

int find(vector<int>& p,int l,int r,int k){
    int h=partition(p,l,r);
    if(h==k){
        return p[k];
    }
    else if(h<k){
        find(p,h+1,r,k);
    }
    else{
        find(p,l,h-1,k);
    }
} 

int main(){
    int n,k;
    cin>>n>>k;
    vector<int> p(n);
    for(int i=0;i<n;i++){
        cin>>p[i];
    }
    int f=find(p,0,n-1,k);
    cout<< f;
} 

by 张心博harry @ 2024-12-27 10:26:30

我也超时了QAQ

by zhangruixiang @ 2024-12-27 12:53:08

@张心博harry@bennini_217 用快速输入输出

#include<bits/stdc++.h>
#define int long long
using namespace std;
int x[5000005],k;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}//快读
inline void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}//快输
signed main()
{
    int n;
    n=read();k=read();
    for(int i=0;i<n;i++)
        x[i]=read();
    sort(x,x+n);
    write(x[k]);
}

by LionBlaze @ 2024-12-27 13:04:11

@bennini_217 k 应该相应减少，而不是不变。

比如 3 在 2\ 2\ 3\ 5\ 4 中是第 2 小，但是在 3\ 5\ 4 中是第 0 小。

by LionBlaze @ 2024-12-27 13:06:39

@zhangruixiang

首先，这并不是正解。正解是 O(n) 做法。

然后，你的快读快写不够快啊，用的是 getchar，会加锁，建议看【模板】快速读入 一题。

by 张心博harry @ 2024-12-27 14:01:17

@LionBlaze

正确

by 张心博harry @ 2024-12-27 14:01:37

%%%

by bennini_217 @ 2024-12-27 16:12:11

@LionBlaze但是我这里k，l，r都表示序号数，应该是不用改变的呀