二分TLE求助

Winter_and_Autumn @ 2024-12-24 13:08:51

#include<bits/stdc++.h>
using namespace std;
int n,a[5000005],k;
void qsort(const int L,const int R){
    int r=R,l=L,mid=a[(R+L)>>2];
    do{
        while(a[r]>mid)r--;
        while(a[l]<mid)l++;
        if(l<=r)swap(a[l],a[r]),l++,r--;
    }while(l<=r);
    //L<=r<=l<=R
    if(k<r+1)qsort(L,r);
    else if(k>l-1)qsort(l,R);
    else {
        cout<<a[r+1];
        return ;
    }
}
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>a[i];
    qsort(0,n-1);
    return 0;
}

by Peaky @ 2024-12-24 13:52:23

注意，\frac{x}{2}=x>>1 而非 x>>2。

#include<bits/stdc++.h>
using namespace std;
int n,a[5000005],k;
void qsort(const int L,const int R){
    int r=R,l=L,mid=a[(R+L)>>1]; //
    do{
        while(a[r]>mid)r--;
        while(a[l]<mid)l++;
        if(l<=r)swap(a[l],a[r]),l++,r--;
    }while(l<=r);
    //L<=r<=l<=R
    if(k<r+1)qsort(L,r);
    else if(k>l-1)qsort(l,R);
    else {
        cout<<a[r+1];
        return ;
    }
}
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    qsort(0,n-1);
    return 0;
}

by Peaky @ 2024-12-24 13:53:15

输入可以考虑用 scanf

by Peaky @ 2024-12-24 13:53:51

@Winter_and_Autumn

by Winter_and_Autumn @ 2024-12-25 13:07:31

@Peaky感谢大佬帮助