求助！！！为什么超时了？

Sasanguk @ 2023-11-28 20:57:00

#include <iostream>
using namespace std;

const int MAX=5000001;
int n,num[MAX],k;
void quick_sort(int num[],int l,int r)
{
    if(l>=r)
        return;
    int x=num[(l+r)/2];
    int i=l-1,j=r+1;
    while(i<j)
    {
        do
        {
            i++;
        }while(num[i]<x);
        do
        {
            j--;
        }while(num[j]>x);
        if(i<j)
            swap(num[i],num[j]);
    }
    quick_sort(num,l,j);
    quick_sort(num,j+1,r);
}
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>num[i];
    quick_sort(num,0,n-1);//快排
    cout<<num[k]<<endl;
    return 0;
}

by UzumakiBoruto @ 2023-11-28 21:15:39

因为快排的复杂度是 O(n \log n) ,速度不够快。我用 sort 也有两个点 TLE 了

#include<bits/stdc++.h>
using namespace std;
int s[5000000];
int main()
{
    int n,k;
    scanf("%d %d",&n,&k);
    for (int i=0; i<n; i++) scanf("%d",&s[i]);
    sort(s,s+n);
    printf("%d",s[k]);
    return 0;
}

一样超时

by UzumakiBoruto @ 2023-11-28 21:17:03

评测记录

by wangzhiqin @ 2023-11-28 21:23:37

@Sasanguk 快排？

1≤n<5000000

快排是n log n 你猜超不超时 建议直接无视题目所说的“请不要使用nth_element"

或者你看那第一个题解

by Plutopro @ 2023-12-07 23:54:52

cin没有取消同步

by agr123456 @ 2023-12-09 17:44:39

ios::sync_with_stdio(false); cin.tie(0); 用快读可以过，加上这两行和开O(2)试试

by H2230819090 @ 2023-12-13 20:42:37

@UzumakiBoruto cin有一个缓冲区，把cin换成scanf会快点，不会超时，尽量不用sort来做，用分治算法，来提高自身的编程能力

by limingle01 @ 2023-12-15 19:52:38

输入换成这个： for(int i=0;i<=n;i++){ scanf("%d",&a[i]); }

by ljk654321 @ 2023-12-16 09:12:16

#include<bits/stdc++.h>
using namespace std;
int a[100000001];
int read(){
    int x = 0 , f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
int main()
{
    long long n , k;
    n = read() , k = read();
    for(int i = 0 ; i < n ; i++)
    a[i] = read();
    sort(a , a + n) ;   
    cout << a[k];
    return 0;
}