部分快排TLE，求助！

Lhw_666 @ 2020-12-20 09:51:35

#include <bits/stdc++.h>
using namespace std;

int swap(int arr[], int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

int *partition(int arr[], int L, int R){
    int less = L-1;
    int more = R;
    for(int i = L; i < more;){
        if(arr[i] < arr[R]){
            swap(arr, i++, ++less);
        }else if(arr[i] > arr[R]){
            swap(arr, i, --more);
        }else{
            i++;
        }
    }
    swap(arr, more, R);
    return new int [2] {less+1, more};
}

void quickSort(int arr[], int L, int R, int K){
    if(L < R){
        int *p = partition(arr, L, R);
        if(K < p[0]){
            quickSort(arr, L, p[0]-1, K);
        }else if(K > p[1]){
            quickSort(arr, p[1]+1, R, K);
        }
        else if (K >= p[0] && K <= p[1]){
            cout << arr[p[0]];
            return;
        }
    }else if(L==R){
        cout << arr[K];
    }
}

int *arr = new int [1000000000];
int main(){
    int n, K;
    cin >> n >> K;
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    quickSort(arr, 0, n-1, K);
}

by Lhw_666 @ 2020-12-20 09:56:02

#include <bits/stdc++.h>
using namespace std;

int swap(int arr[], int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

int *partition(int arr[], int L, int R){
    int less = L-1;
    int more = R;
    for(int i = L; i < more;){
        if(arr[i] < arr[R]){
            swap(arr, i++, ++less);
        }else if(arr[i] > arr[R]){
            swap(arr, i, --more);
        }else{
            i++;
        }
    }
    swap(arr, more, R);
    return new int [2] {less+1, more};
}

void quickSort(int arr[], int L, int R, int K){
    if(L < R){
        int *p = partition(arr, L, R);
        if(K < p[0]){
            quickSort(arr, L, p[0]-1, K);
        }else if(K > p[1]){
            quickSort(arr, p[1]+1, R, K);
        }
        else if (K >= p[0] && K <= p[1]){
            cout << arr[p[0]];
            return;
        }
    }else if(L==R){
        cout << arr[K];
    }
}

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int *arr = new int [100000000];
int main(){
    int n, K;
    cin >> n >> K;
    for(int i = 0; i < n; i++)
        arr[i] = read();
    quickSort(arr, 0, n-1, K);
}

加了个快读居然就过了QAQ

by szkzyc @ 2020-12-20 09:58:57

这题正解是分治啊

by 老子是北瓜 @ 2020-12-20 09:59:11

@Lhw_666 我觉得你可能就是因为没用快读T的

by Lhw_666 @ 2020-12-20 10:00:49

cin也太坑了吧，直接把cin换成scanf，直接就过了，我吐了

by Lhw_666 @ 2020-12-20 10:01:39

@szkzyc 我这就是分治吧

by Lhw_666 @ 2020-12-20 10:02:30

@老子是北瓜 确实，cin太慢了，我换成scanf就过了，快读都不用不上，哭了，浪费了好长时间

by szkzyc @ 2020-12-20 10:02:33

@Lhw_666 代码没细看，但我觉得这题可以不用快读

by Lhw_666 @ 2020-12-20 10:05:48

@szkzyc 对的，我之所以TLE，是因为用了cin，换成scanf就好了，快读也用不到了，感谢回复！