为什么sort会TLE

Qiqi_Hun @ 2023-08-28 10:39:17

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[5000005],k,n;
signed main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    cout<<a[k];
    return 0;
}

by ninji @ 2023-08-28 10:40:05

@hunjingqi sort 时间复杂度：O(n^2)

by ninji @ 2023-08-28 10:40:16

@hunjingqi 开一下O2优化

by ninji @ 2023-08-28 10:42:12

@ninji 说错了 O(nloogn)

by ninji @ 2023-08-28 10:42:49

@hunjingqi 用scanf和printf

by ninji @ 2023-08-28 10:43:42

@hunjingqi

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
long long a[5000000]={0};
int main()
{
    long long n,m;
    scanf("%lld%lld",&n,&m);
//  cin >> n >> m;
    for(int i=0;i<n;i++)
    scanf("%lld",&a[i]);
//  cin >> a[i];
    sort(a,a+n);
printf("%lld",a[m]);
 } 

by Argvchs @ 2023-08-28 10:49:53

@hunjingqi 用 nth_element

by Msents @ 2023-08-28 10:50:19

@hunjingqi 读入慢了，cin cout 要用

ios::sync_with_stdio(false);

不然会很慢（使用后printf/scanf和cin/cout不能混用）

cin.tie(nullptr);

还可以使用上面这一句进一步加速，但缺点是读入输出不同步，要手动刷新缓冲区

by Qiqi_Hun @ 2023-08-28 10:50:59

@Argvchs 什么是nth_element?

by ninji @ 2023-08-28 10:53:43

@hunjingqi https://blog.csdn.net/Zhengyangxinn/article/details/106683107

by Argvchs @ 2023-08-28 10:54:37

@hunjingqi https://zh.cppreference.com/w/cpp/algorithm/nth_element