60!

信息学carryHarry @ 2021-05-18 20:40:33

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n,k,a[50000005];
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+1+n);
    cout<<a[k+1];
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,k,a[5000005],tmp[5000005],ans=0;
void mergesort(int lt,int rt)
{
    if(lt==rt)
        return ;
    long long mid=(lt+rt)/2;
    mergesort(lt,mid);
    mergesort(mid+1,rt);
    long long i=lt,j=mid+1,p=lt;
    while(i<=mid&&j<=rt)
    {
        if(a[i]<=a[j])
            tmp[p++]=a[i++];
        else{
            tmp[p++]=a[j++];
            ans+=mid-i+1;
        }
    }
    while(i<=mid)
        tmp[p++]=a[i++];
    while(j<=rt)
        tmp[p++]=a[j++];
    for(int k=lt;k<=rt;k++)
        a[k]=tmp[k];
    return ;
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    mergesort(1,n); 
    cout<<a[k+1];
    return 0;
}

by _caiji_ @ 2021-05-18 20:44:25

两个都是 O(n\log n) 的错解，所以过不了，想一想怎么把时间复杂度优化到 O(n)

by _Emiria_ @ 2021-05-18 20:48:02

此题卡 nlogn 啊

by _Emiria_ @ 2021-05-18 20:52:24

@caijianhong 为什么我 O(n\log{n}) 加快读卡过去了？？？

by 信息学carryHarry @ 2021-05-18 20:56:04

那用插入排序

by CGDGAD @ 2021-05-18 20:57:36

@信息学carryHarry 然而插排更慢

by Forever1507 @ 2021-05-18 20:58:55

@信息学carryHarry 写个快读

by 信息学carryHarry @ 2021-05-22 19:50:27

@国服墨子 不需要

by 信息学carryHarry @ 2021-05-23 20:34:20

用快排

by 信息学carryHarry @ 2021-05-23 20:35:05

#include<bits/stdc++.h>
using namespace std;
int n,k,a[5000005],tmp[5000005],ans=0;
void qs(int lt,int rt)
{
    if(lt>=rt)
    {
        if(k == lt){
            cout<<a[k];
            exit(0);
        }
        return ;
    }

    int i=lt,j=rt;
    while(i<j)
    {
        while(i<j&&a[j]>=a[lt])
            j--;
        while(i<j&&a[i]<=a[lt])
            i++;
        swap(a[i],(i==j)?a[lt]:a[j]);
    }
    if(k==i)
    {
        cout<<a[k];
        exit(0);

    }
    else if(k<i)
        qs(lt,i-1);
    else
        qs(j+1,rt);
    return ;
}
int main()
{
    scanf("%d %d",&n,&k);
    k++;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    qs(1,n); 
    return 0;
}