心态要炸了呀，求帮忙

Carrot_Rui @ 2020-09-19 13:15:25

#include<bits/stdc++.h>
using namespace std;
long long a[6666666];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    printf("%d",a[m+1]);

    return 0;
}

by xzllll07 @ 2020-09-19 13:42:40

STL 有 nth_element 函数。

by zhanghzqwq @ 2020-09-19 13:42:42

@xzllll 我快读+火车头过了

by zhanghzqwq @ 2020-09-19 13:43:19

事实证明O(n)卡O(nlogn)很难卡

by Rui_R @ 2020-09-19 13:45:28

@Suxianrui666

#include <algorithm>
std::nth_element(a+1,a+k+1,a+n+1);

效果为，a[k+1]会成为题目要你算的东西。

by xzllll07 @ 2020-09-19 13:48:29

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int s = 0, w = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}
int a[5000005];
int n,k;
int main()
{
    n=read();
    k=read();
    for(register int i=0;i<n;++i)
    {
        a[i]=read();
    }
    sort(a,a+n);
    printf("%d",a[k]);
    return 0;
}

好像确实能卡过去。。。

by zhanghzqwq @ 2020-09-19 13:49:11

@xzllll 还挺快

by zhanghzqwq @ 2020-09-19 13:50:22

@Suxianrui666 O(n)的代码这么写：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[5000005],k,n;
void qsort(int l,int r){
    int i=l,j=r,mid=a[(l+r)>>1];
    while(i<=j){
        while(a[i]<mid){
            i++;    
        }
        while(a[j]>mid){
            j--;
        }
        if(i<=j){
            swap(a[i],a[j]);
            i++;
            j--;
        }
    }
    if(i<=k){
        qsort(i,r);
    }else if(k<=j){
        qsort(l,j);
    }else{
        printf("%d\n",a[j+1]);
        return;
    }
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    qsort(0,n-1);
    return 0;
}

by Carrot_Rui @ 2020-09-19 14:06:45

@zhanghanzhang

大佬就是大佬，菜鸡我，哎；

快noi初赛了，您们有没有什么建议吗。

学习什么好？

——对我这个菜鸟而言。

by zhanghzqwq @ 2020-09-19 14:35:49

@Suxianrui666 往死了刷洛谷有题就行（我就是这么干的）

by impuk @ 2020-09-19 15:16:33

https://www.luogu.com.cn/record/list?user=279700&pid=P1177&orderBy=1&status=&page=1

建议松基