80分求助！最后一个点TLE！

pooooo @ 2021-01-04 20:40:33

var 
  a:array[0..5000000] of longint;
  n,i,m:longint;
   procedure qsort(l,r:longint);//快排
    var i,j,t,mid:longint;
     begin
      i:=l;
      j:=r;
      mid:=a[(l+r)div 2];
       repeat
        while(a[i]<mid) do inc(i);
        while(a[j]>mid) do dec(j);
       if i<=j then
        begin
         t:=a[i]; a[i]:=a[j]; a[j]:=t;
         inc(i); dec(j);
        end;
       until i>j;
      if l<j then qsort(l,j);
      if i<r then qsort(i,r);
     end;
   begin
    readln(n,m);
     m:=m+1;
    for i:=1 to n do read(a[i]); 
    qsort(1,n);
    writeln(a[m]);
   end.

by _Empty @ 2021-01-04 20:48:56

c++路过

by _Lionel @ 2021-01-04 20:53:26

c++路过*2

by CGDGAD @ 2021-01-04 20:54:21

c++路过

by _caiji_ @ 2021-01-04 21:01:17

算法复杂度就不对吧，不能直接做O(n\log n)的快排，每次快排会把数据分成两块有序的部分，这时就不需要两边都调用，只用递归调用一边就行了

by 123456zmy @ 2021-01-04 21:13:54

c++路过*4并表示sort可过

by little_kongbai @ 2021-01-04 21:19:38

@123456zmy sort实测60pts

by pooooo @ 2021-01-04 21:20:51

@caijianhong 没有理解诶，现在是认为是判断第k小数在分割出来的两份中的左边还是右边来简短时间（就是不理解咋用递归来做）

by little_kongbai @ 2021-01-04 21:21:26

@123456zmy sort后大概是1e8多一点 所以后两个点TLE

by 123456zmy @ 2021-01-04 22:01:35

@kongbaijun sort 开 O2 再加个 fread 就是 800msAC

by Almond7216 @ 2021-02-05 15:37:54

@123456zmy sort平均 n log n,此处n<=5000000，会超时