SSL 1421求第k小数

题目

直接用一个结构体分别存储存原下标和数值，排序之后输出第k个数原来的下标就好了(因为是有序的，所以第K个数就是第K小的数)。

Code

#include<algorithm>
#include<iostream>
#include<cstdio>
#define sco 40000
using namespace std;
int n,k,x;
struct node{
	int dt,id;
}a[sco];
void qs(int l,int r){						//手写快排
	if(l>=r) return;
	int i=l,j=r,t=a[(l+r)/2].dt;
	do{
		while(a[i].dt<t and i<=r) i++;
		while(a[j].dt>t and j>=l) j--;
		if(i<=j){
			swap(a[i],a[j]);
			i++;j--;
		}
	}while(i<=j);
	qs(l,j);
	qs(i,r);
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i].dt);				//下标与数值的存储
		a[i].id=i;
	}
	qs(1,n);
	printf("%d",a[k].id);					//输出
	return 0;
}