全TLE，求助！

justinjia @ 2020-08-27 08:00:55

#include"stdio.h"
void bubblesort(int a[],int end){//冒泡排序（我使用比较熟练的一种排序算法）
    for(int i=0;i<=end;i++)
        for(int j=end;j>i;j--)
            if(a[j-1]>a[j]){
                int t=a[j];
                a[j]=a[j-1];
                a[j-1]=t;
            }
}
int main(void){
    int n,k;
    scanf("%d%d",&n,&k);
    int a[n];
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    bubblesort(a,n-1);
    printf("%d",a[k]);
    return 0;
}

by 水题王子 @ 2020-08-27 08:01:44

显然是的（

by 迷残云 @ 2020-08-27 08:01:59

看好数据范围

by 一只小H @ 2020-08-27 08:03:59

直接sort都快过不了了，更别说冒泡了……

by LucasXu80 @ 2020-08-27 08:07:22

这题极其卡常（

by FutureThx @ 2020-08-27 08:10:18

@justinjia 使用快排加快读，包你代码快到飞起

by justinjia @ 2020-08-27 08:13:05

@一只小HQAQ 我倒想问问你sort用的是什么排序算法？

by justinjia @ 2020-08-27 08:14:23

@Ymw123 你说的快读是什么东西？scanf难道还不够快吗？

by panzhicun @ 2020-08-27 08:20:18

@justinjia 快读更快

by FutureThx @ 2020-08-27 08:20:45

@justinjia

#include <iostream>
using namespace std;
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 main()
{
    int a;
    //cin >> a;
    a = read();
    cout << a;
    return 0;
}

把 read 函数封装起来，读入就用把原来的

cin >> 变量;

改为

变量 = read();

读入单个字符然后处理速度会快很多

by Chinshyo @ 2020-08-27 08:22:53

@justinjia 冒泡排序是 O(n) 时间复杂度，快排是 O(2^1.3) 的时间复杂度。明显选用快排。不会手打就直接用sort。实在觉得不稳就加个cmp就是了