正解方法(分治)TLE(60pts)

_8008008 @ 2023-07-31 20:25:58

#include<iostream>
using namespace std;
int n,a[5000000],k;
void SORT(int l,int r){
    int l2=l,r2=r,cmp=0;
    if(l>=r)return;
    while(l!=r){
        if(a[r]<a[l]){
            int c=a[r];a[r]=a[l],a[l]=c;
            cmp=!cmp;
        }
        if(cmp)r--;else l++;
    }
    if(k<l)SORT(l2,l-1);
    else if(k>l)SORT(r+1,r2);
    else return;
}
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>a[i];
    SORT(0,n-1);
    cout<<a[k];
    return 0;
}

by ilyFurina @ 2023-08-01 16:19:33

sort的方法肯定过不了，数据范围是5*10^6，sort的 n \cdot log(n)算出来大概是一千万，有些极限,，可以尝试常数优化，但还是应该考虑正解：根据快排思想来寻找第 k 小的数。

不能直接采用排序然后输出的方法。 用分治方法，先任意找数组中的一个元素pivot，采用快速排序将数组进行一次划分，小于pivot的元素left，大于pivot的元素放right。然后判断元素pivot是否满足题目为第k小的数，满足则直接输出，否则判断下一次在哪一区间进行划分。

换句话说，就是在快排中找第k小的数

by _8008008 @ 2023-08-02 09:53:25

@irybo 就是这种思路

    if(k<l)SORT(l2,l-1);
    else if(k>l)SORT(r+1,r2);
    else return;

by ilyFurina @ 2023-08-02 13:25:47

抱歉 没认真看 你这个问题应该出在读入上 因为题目里可能读入了5*10^6左右的数据，这种情况下使用cin/cout会非常慢，我手写了一个快速读入在评测就过了（当然你也可以试试scanf，至少比cin快得多）

#include<iostream>
using namespace std;
int n,a[5000000],k;

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;
}

void SORT(int l,int r){
    int l2=l,r2=r,cmp=0;
    if(l>=r)return;
    while(l!=r){
        if(a[r]<a[l]){
            int c=a[r];a[r]=a[l],a[l]=c;
            cmp=!cmp;
        }
        if(cmp)r--;else l++;
    }
    if(k<l)SORT(l2,l-1);
    else if(k>l)SORT(r+1,r2);
    else return;
}
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>a[i];
    SORT(0,n-1);
    cout<<a[k];
    return 0;
}

加入后最后两个点用时大概250ms