归并排序求优化

P1923 【深基9.例4】求第 k 小的数

ABCgfed @ 2023-07-03 17:37:21

60pts

#include<bits/stdc++.h>
using namespace std;
const int N=5e6+8;
int n,a[N],q[N],k;
void merge_sort(int q[],int l,int r){
    if(l>=r) return ;
    int mid=(l+r)/2;
    merge_sort(q,l,mid);
    merge_sort(q,mid+1,r);
    int k=1,i=l,j=mid+1;
    while(i<=mid&&j<=r){
        if(q[i]<=q[j]) a[k++]=q[i++];
        else a[k++]=q[j++];
    }
    while(i<=mid) a[k++]=q[i++];
    while(j<=r) a[k++]=q[j++];
    for(i=l,j=1;i<=r;i++,j++) q[i]=a[j];
    return ;
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&q[i]);
    }
    merge_sort(q,1,n);
    printf("%d\n",q[k+1]);
    return 0;
}

by hjqhs @ 2023-07-03 17:56:43

@ABCgfed 不行 这道题正解是nth_element或快排


by Happy_Orca @ 2023-07-03 21:29:15

@ABCgfed 不行,写分治吧


|