二分法,,全部re,求调
查看原帖
二分法,,全部re,求调
1330072
Relisc楼主2024/8/8 23:44
#include <bits/stdc++.h>
using namespace std;
int n,k;
int a[5000000];

int quicksort(int l,int r)
{
	if(l == r)	return a[l];
	int i=l-1,j=r+1;
	int x=a[(l+r)>>1];
	while(i<j)
	{
		do i++;while(a[i]<x);
		do j--;while(a[j]>x);
		if(i<j)	swap(a[i],a[j]);
	}
	//经过一次快排后,中间位置的数已经被确定,且它左边的数都比它小,右边的数都比它大; 
	//如果k<=j,则说明第k小的数,只能在左边,否则只能在右边。 
	if(k<=j)	return quicksort(l,j);
	else	return quicksort(j+1,r);
}

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

2024/8/8 23:44
加载中...