【SSL_1421】求第K小数

求第K小数

Description

于给定n个元素的数级a[1…n]，要从中找出第k小的元素。

Input

第一行是总数n和k，第二行是n个待比较的数。

Output

第K小数的位置。

Sample Input

5 3
23 8 91 56 4

Sample Output

1

---

题解

用快排，在快排的过程中求第k小。
因为快排每次都会把比key小的的数放在左边，把比key大的数放在右边，
所以每次排完后，若key在第 i i i个位置，则key是第 i i i小的数。
若： i = k i=k i=k则找到第 k k k小的数，输出； i < k i<k i<k则只用往右递归； i > k i>k i>k则只用往左递归

代码

#include<queue>
#include<iostream>
#define ll unsigned int //unsigned 是为了抢最优解
#define M 1000001
using namespace std;
struct node
{
	ll num,id; //num是数，id是位置
} a[M];
ll n;
void qsort(ll k,ll l,ll r)
{
	ll i=l,j=r,key=a[((l+r)>>1)].num;
	if(i>j) return;
	while(i<j)
	{
		while(a[i].num<key&&i<j) i++; //从左往右找比key大的数
		while(a[j].num>key&&j>i) j--; //从右往左找比key小的数
		swap(a[i],a[j]);
	}
	if(k==i) cout<<a[i].id; //找到第k小的数
	if(k<i) qsort(k,l,i-1); //往左递归
	if(k>i) qsort(k,i+1,r); //往右递归
}
int main()
{
	ll k;
	scanf("%d%d",&n,&k);
	for(ll i=1; i<=n; a[i].id=i,i++) scanf("%d",&a[i].num);
	qsort(k,1,n);
}