轩酱自带逆风 @ 2022-07-21 11:25:59
#include<bits/stdc++.h>
using namespace std;
const int N=5000005;
int q[N],n,k;
void quick_sort(int q[],int l,int r){
if(l>=r)return ;
int x=q[(l+r)/2],i=l-1,j=r+1;
while(i<j){
do i++;while(q[i]<x);
do j--;while(q[j]>x);
if(i<j)swap(q[i],q[j]);
}
quick_sort(q,l,j);
quick_sort(q,j+1,r);
}
int main(){
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)scanf("%d",&q[i]);
quick_sort(q,0,n-1);
printf("%d",q[k]);
return 0;
}
by BugGod @ 2022-07-21 11:51:21
不需要这么麻烦,只要std::sort+吸氧就行了
by BugGod @ 2022-07-21 11:54:06
直接快排不太行,
by BugGod @ 2022-07-21 11:59:51
我们可以借助快排的分治思想,在每次将数列分成三部分后处理。
by BugGod @ 2022-07-21 12:07:03
只要确定区间就在区间里搜索,不需要考虑别的地方,以此优化。
另外,既然出题人温馨提示,我们也可以用
nth_element函数
用法如下:
nth_element(x,x+k,x+n)
输出
虽然
by 轩酱自带逆风 @ 2022-08-11 09:59:33
@luoyida 感谢