为啥只得80分,还有20分超时??????大佬求解

P1923 【深基9.例4】求第 k 小的数

7teen @ 2022-05-06 15:09:58

#include <bits/stdc++.h>
using namespace std;
int t;
int a[5000005];
void quick_sort(int left,int right)
{
    int i=left,j=right;
    int pivot = a[ ( left + right ) / 2];

    do{
        while(a[j]>pivot)
        {
            j--;
        }
        while(a[i]<pivot)
        {
            i++;
        }
        if(i<=j)
        {
            swap(a[i],a[j]);
            i++;
            j--;
        }
      }while(i<=j);

        if(t<=j)
        {
            quick_sort(left,j);
        }
        else if(i<=t)
        {
           quick_sort(i,right);
        }
        else
        {
            cout<<a[j+1];
            exit(0);
        }       
}

int main()
{
    int n;
    cin>>n>>t;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    quick_sort(0,n-1);
    return 0;
}

by Somecat_W @ 2022-05-06 15:21:37

cin 的速度很慢,对于输入量很大的题目(如此题)请使用 scanf 或者在主函数开头处加入这句话:

ios::sync_with_stdio(false);

by chs_is_sb @ 2022-05-06 15:32:24

快读不好吗?


by cfkk @ 2022-05-06 15:36:22

@17djm 就是卡你那种算法的


by Super_Supper @ 2022-05-06 15:48:00

@cfkk ???我不理解,这题不用这个用啥,用你那个当成宝的 nth_element 吗?


by Zvelig1205 @ 2022-05-06 20:31:55

这题不是平衡树吗


by Super_Supper @ 2022-05-10 20:10:05

@思考人生中 您看清楚,这题确实是用快排写的


|