2414: 【作】【普及/提高-】【P1923】求第 k 小的数
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：28
解决：27
题目描述
输入 （ 且 为奇数）个数字 （），输出这些数字的第 小的数。最小的数是第 小。
请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。
样例输入 复制
5 1
4 3 2 1 5样例输出 复制
2提示
#include<bits/stdc++.h>
using namespace std;
int a[5000010],n;
int ans=0,k;// 记录答案，以及求第k小。k是已知值，比如在main函数中赋值过
void findkth(int a[],int l,int r){ //引人数组的地址
if(l==r) {
ans=a[l];// 区间长度为1时，记录答案
return;
}
int i = l, j = r, flag = a[(l + r) / 2], tmp;
do {
while (a[i]<flag)i++; //从左找比哨兵大的数
while (a[j]>flag)j--; //从右找比哨兵小的数
if (i<=j){ //交换
tmp=a[i];a[i]=a[j];a[j]=tmp;
i++;j--;
}
} while (i <= j);
if (k <= j)findkth(a,l,j); //第k小的数字在左区间
else if (i <= k)findkth(a,i,r); //第k小的数字在右区间
else findkth(a,j+1,i-1); //第k小的数字既不在左区间，也不在右区间
}
int main(){
std::ios::sync_with_stdio(false);
cin>>n>>k;
for (int i=0;i<n;i++)
cin>>a[i];
findkth(a,0,n-1);
cout<<ans;
return 0;
}