归并排序求优化
查看原帖
归并排序求优化
764239
ABCgfed楼主2023/7/3 17:37

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;
}
2023/7/3 17:37
加载中...