救救孩子吧！

大白菜ac @ 2020-05-05 18:40:41

#include <iostream>
#include <climits>
using namespace std;
int a[5000002];
const int INFTY=INT_MAX;
void Swap(int i,int j){
    int temp=a[i];a[i]=a[j];a[j]=temp;
}
int Partiton(int left,int right){
    int i=left,j=right+1;
    do{
        do i++;while(a[i]<a[left]);
        do j--;while(a[j]>a[left]);
        if(i<j)Swap(i,j);
    }while(i<j);
    Swap(left,j);
    return j;
}
void Search(int left,int right,int &x,int k){
    int j=Partiton(left,right);
    if(k==j){
        x=a[j];return;
    }
    else if(k<j)return Search(left,j-1,x,k);
    else return Search(j+1,right,x,k-j);
}
int main(){
    int n,k,x;
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>a[i];
    a[n]=INFTY;
    Search(0,n-1,x,k);
    cout<<x;
    return 0;
} 

by 已注销ZdCpmQy3 @ 2020-05-05 18:45:54

sort+读入优化+输出优化+O2即可

by 人间温柔 @ 2020-05-05 19:45:49

优先队列就可以了 定义如下：

提示一下啊

by 人间温柔 @ 2020-05-05 19:48:39

priority_queue<int>pq;

by 人间温柔 @ 2020-05-05 23:16:37

@18111207031dsz 回复你了哈

by 大白菜ac @ 2020-05-06 11:43:01

@永不放弃 我想知道我错在哪？最后两个TLE。

by 人间温柔 @ 2020-05-06 11:59:02

@18111207031dsz 时间超了，你再看一下Partiton和Search能不能再优画一下？

by 人间温柔 @ 2020-05-06 23:33:24

@18111207031dsz 我也做了一下这道题 其实呢你想复杂了，没必要那么麻烦。 下面是我的代码，希望对你有帮助哦~

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
long long n;
long long k;
long long a[5000005];
inline long long read()
{
    char c;
    long long num=0;
    long long f=1;
    c=getchar();
    while(c<'0' || c>'9')
    {
        if(c=='-')
        {
            f=-1;
        }
        c=getchar();
    }
    while(c>='0' && c<='9')
    {
        num=num*10+c-'0';
        c=getchar();
    }
    return num*f;
}
int main()
{
    n=read();
    k=read();
    for(long long i=1;i<=n;i++)
    {
        a[i]=read();
    }
    sort(a+1,a+n+1);
    cout<<a[k+1];
    return 0;
}

其实就是一个sort排序，再加上输入输出优化，但是别忘了提交的时候要开O2哦

by 大白菜ac @ 2020-05-07 18:33:35

@永不放弃 谢谢大佬，那个O2有啥用？

by 人间温柔 @ 2020-05-08 12:31:44

@18111207031dsz 不客气，其实我也不知道O2有啥用，我是先写好代码提交之后最后2个点WA，看题节后才知道要开O2 不过呢你也不用太紧张，我这个代码复杂度是O(n)，NOIP或CSP不会计较O2的

by Guan_qiqi @ 2020-05-09 20:17:47

试试STL 的nth_element()函数

这题卡的严，不要用cin和cout，依然会最后两个TLE

改用scanf和printf能过。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n, k;
    scanf("%d%d", &n, &k);
    int a[n];
    for(int i=0; i<n; i++){
        scanf("%d", &a[i]);
    }

    nth_element(a, a+k, a+n);

    printf("%d", a[k]);

    return 0;
}