60分后两个TLE求救

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

mazel @ 2023-08-02 16:32:57

一直60分,前三个点过了,后两个一直TLE

#include<iostream>
using namespace std;

int a[5000005] = { 0 };
int k = 0;
void swap(int& a, int& b)
{
    int c = a;
    a = b;
    b = c;
}
int quick_find( int l, int len) //   l代表起始位置,len代表终止位置
{
    if (l >= len)
        return a[l];
    int mid = a[rand() % (len - l) + l];
    int ak = len, j = l, i = l;          //ak代表大于mid的值(k--),j代表小于min的值
    while (i < ak)
    {
        if (a[i] < mid)
            swap(a[i++], a[j++]);
        else if (a[i] > mid)
            swap(a[i], a[--ak]);
        else
            i++;
    }
    //判断ak与j的大小判断在前半段还是后半段
    if (k < j)
    {
        return quick_find(l , j);
    }
    else if (k >= ak)
    {
        return quick_find(ak, len);
    }
    else
        return mid;
}

int main()
{

    int n = 0;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    cout << quick_find(0, n) << endl;
}

by __DIOsama__ @ 2023-08-02 16:38:49

建议加个std::ios::sync_with_stdio(false)


by __DIOsama__ @ 2023-08-02 16:40:02

@mazel


by mazel @ 2023-08-02 22:02:08

@DIO__ 请问是加在哪个位置呢


by __DIOsama__ @ 2023-08-03 08:20:55

@mazel

int main()
{
    std::ios::sync_with_stdio(false);
    int n = 0;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    cout << quick_find(0, n) << endl;

}

by mazel @ 2023-08-03 12:37:52

@DIO__ 谢谢大佬,这样写就可以使cin和scanf的读入速度一样了是吧,我发现把cin全部改成scanf输入也可以加快速度,这两种方法都不会超时,感谢。


|