大佬们为啥我一个WA,两个TLE啊

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

ziqikang @ 2024-10-19 19:58:55

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

long long a[6000000],b[6000000];
long long n,k;
void msort(long long arr[],long long brr[],long long l,long long r)
{
    if (l >= r) return;
    long long mid = (l + r) / 2;
    msort(arr,brr,l,mid),msort(arr,brr,mid + 1,r);
    long long i = l,j = mid + 1,k = l;
    while (i <= mid && j <= r)
    {
        if (arr[i] <= arr[j])
        {
            brr[k] = arr[i];
            k++,i++;
        }
        else
        {
            brr[k] = arr[j];
            k++,j++;
        }
    }

    while (i <= mid)
    {
        brr[k] = arr[i];
        k++,i++;
    }
    while (j <= r)
    {
        brr[k] = arr[j];
        k++,j++;
    }
    for (int i = l;i <= r;i++)
    {
        arr[i] = brr[i];
    }
}

int main()
{
    cin >> n >> k;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    msort(a,b,1,n);
    cout << a[k];
    return 0;
}

------------

by medal_dreams @ 2024-10-19 20:09:05

这个程序必须是 O(n) 的但是你这是归并是 O(nlogn) 的,所以不对


by ziqikang @ 2024-10-19 20:24:06

@medal_dreams 谢谢


by yanghaoyu123 @ 2024-10-19 21:26:48

@ziqikang 用sort直接秒了,但是必须用scanf和printf,否则会TLE,但如果想练算法的话那就别用了


by hehaoze @ 2024-10-24 23:05:30

@yanghaoyu123 用sort那他让你练啥


|