userjp @ 2023-11-03 23:38:18
题目：P1923 【深基9.例4】求第 k 小的数 我的代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 5000005;
int is1[N],temp[N];
void merge(int a,int mid,int b){
int i = a,j = mid + 1,k = a;
while(i<=mid&&j<=b){
if(is1[i]<is1[j]) temp[k++] = is1[i++];
else temp[k++] = is1[j++];
}
while(i<=mid) temp[k++] = is1[i++];
while(j<=b) temp[k++] = is1[j++];
for(int i = a;i<=b;i++){
is1[i]=temp[i];
}
}
void mergesort(int a,int b){
if(a>=b) return;
int mid = (a+b)/2;
mergesort(a,mid);
mergesort(mid+1,b);
merge(a,mid,b);
}
int main(){
int n,m;
scanf("%d %d ",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&is1[i]);
}
mergesort(1,n);
printf("%d",is1[m+1]);
return 0;
}真不懂啊兄弟们
by GaIaxy @ 2023-11-03 23:44:17
用完整排序都不大行，用快排思想，但每次只排k的一边
by yanhao40340 @ 2023-11-04 06:51:28
用基数排序
by shb20111113 @ 2023-11-04 08:06:48
@userjp 我用的是nth_element
#include<bits/stdc++.h>
using namespace std;
int x[5000005],k;
int main()
{
int n;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
scanf("%d",&x[i]);
nth_element(x,x+k,x+n);
printf("%d",x[k]);
}by xpc2024 @ 2023-11-05 13:50:57
@yanhao40340 基排也超时了
by userjp @ 2023-11-05 16:39:36
@GaIaxy 这是啥意思，只排k的一边,有代码实现吗
by userjp @ 2023-11-05 16:40:53
@shb20111113 nth_element我知道，但是题目不是说尽量不要用嘛，我直接用快排开O2优化也能过，就是不知道不开优化怎么过
by shb20111113 @ 2023-11-05 17:55:10
@userjp 暴力sort能过
by GaIaxy @ 2023-11-08 14:25:23
@userjp 修改一下快排代码，每一次快排不是把比主元大的放右边，小的放左边吗，如果你要找的元素比主元的位置小，那下一次快排就只排左边，否则只排右面