蒟蒻求助，后两个点在开了氧气后仍然TLE，请问大佬怎么改进？

daonan @ 2022-01-12 19:16:26

#include<bits/stdc++.h>
using namespace std;
bool cmp(string a,string b);
int main()
{
    long long int n=0;
    long long int m=0;
    cin>>n>>m;
    string a[n];
    for(long long int i=0;i<=n-1;i++)
    cin>>a[i];
    sort(a,a+n,cmp);
    cout<<a[m];
}
bool cmp(string a,string b)
{
    if(a.size()==b.size()) return a<b;
    return a.size()<b.size();
}

by yangyuanxi44 @ 2022-01-12 19:18:37

快速排序，sort过不了

by 蔡竣凯 @ 2022-01-12 19:23:14

#include<bits/stdc++.h>
using namespace std;
bool cmp(int a,int b);
int main()
{
    long long int n=0;
    long long int m=0;
    cin>>n>>m;
    int a[10000];
    for(long long int i=0;i<=n-1;i++)
    cin>>a[i];
    sort(a ,a+n,cmp);
    cout<<a[m];
}
bool cmp(int a,int b)
{
    return a < b;
}

by daonan @ 2022-01-12 19:24:35

@yangyuanxi44 哦哦 好的，谢谢大佬！

by daonan @ 2022-01-12 19:26:12

@蔡竣凯 这题肯定要用字符串呀 数字太大了qwq，用int会全re的

by 蔡竣凯 @ 2022-01-12 19:26:41

开long long

by 蔡竣凯 @ 2022-01-12 19:28:13

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n=0;
    long long int m=0;
    cin>>n>>m;
    int a[10000];
    for(long long int i=0;i<=n-1;i++)
    cin>>a[i];
    sort(a ,a+n);
    cout<<a[m];
}

by 蔡竣凯 @ 2022-01-12 19:32:12

建议用nth_element

by 无咕_ @ 2022-01-12 19:32:39

??TLE跟long long有什么关系？？

by 无咕_ @ 2022-01-12 19:34:51

sort是 O(n\log n) 的好像，nth_element好像是 O(n) （我没用过，搜的）

如果你能用某种方法实现 O(1) 静态查询+O(n) 预处理的话可以写论文了（？）

by daonan @ 2022-01-12 19:35:20

@蔡竣凯 我用字符串+快排过了qwq，貌似用数字类型数据我这边都会re（