P1923居然O(N)过不了
查看原帖
P1923居然O(N)过不了
487959
yyc_qwq楼主2022/12/25 17:26
#include<iostream>
#include<math.h>
using namespace std;

int a[5000005],n,k;

void sort(int l,int r){
    int i = l,j = r,mid = a[(l+r)/2];
    do{
        while(a[j] > mid) j--;
        while(a[i] < mid) i++;
        if(i<=j){
            swap(a[i],a[j]);
            i++,j--;
        }
    }while(i <= j);
    if(k <= j) sort(l,j);
    else if(i <= k) sort(i,r);
    else {
        cout << a[j+1] << endl;
        exit(0);
    }
}

int main(){
    cin >> n >> k;
    for(int i=0;i<n;i++) cin >> a[i];
    sort(0,n-1);
    return 0;
}
2022/12/25 17:26
加载中...