sort & 快排 60分！

Accepted喵 @ 2020-09-11 13:01:26

#include<unistd.h>
#include<cstdio>
using namespace std;
const int N=5e6+10;
int a[N],n,k;
void quickSort(int arr[],int left,int right) {
    if (left > right)return;
    int i=left;
    int j=right;
    int base=arr[left];
    while(i!=j) {
        while(arr[j]>=base&&i<j)j--;
        while(arr[i]<=base&&i<j)i++;
        if(i<j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
    arr[left]=arr[i];
    arr[i]=base;
    quickSort(arr,left,i-1);
    quickSort(arr,i+1,right);
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    quickSort(a,0,n);
    printf("%d",a[k+1]);
}

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=5e6+10;
int a[N];
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    sort(a,a+n);
    printf("%d",a[k]);
}

by critnos @ 2020-09-11 13:02:09

O2

by Jsxts_ @ 2020-09-11 13:03:36

快读

by dead_X @ 2020-09-11 13:04:01

优化到O(n)

by Windowsredstone @ 2020-09-11 13:04:06

?

这不是O(n) k小值？

by dead_X @ 2020-09-11 13:06:41

另：拷一份挑战那道题的排序/xyx

by CSP_Sept @ 2020-09-11 13:10:14

这是二分罢

by AT1198_100 @ 2020-09-11 13:11:31

尝试下O^4

by cyffff @ 2020-09-11 13:27:37

O2可过

by Chinese_zjc_ @ 2020-09-11 14:34:02

本题本来就是要用 O(n) 的吧...

by Shirο @ 2020-09-30 11:11:50

#ifdef boost
    #pragma GCC target ("avx2")
    #pragma GCC optimization ("O3")
    #pragma GCC optimization ("unroll-loops")
#endif
#include<bits/stdc++.h>
#define int long long
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
#define __ read()
using namespace std;
const int maxn(5e6+5);
void rda(int *a,int n){for(int i=1;i<=n;++i)a[i]=__;}
void print(int *a,int n){for(int i=1;i<=n;++i)printf("%lld ",a[i]);puts("");}
int n,a[maxn]; 
signed main()
{
    n=__;int k=__;
    rda(a,n);
    sort(a+1,a+n+1);
    cout<<a[k+1];
}

AC了