网站开发公司首页wordpress 政务

1.洛谷题P1923 求第k小的数 

 

题目描述

输入 n（1≤n<5000000 且 n 为奇数）个数字ai​（1≤ai​<109），输出这些数字的第 k 小的数。最小的数是第 0 小。

请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。

输入格式

无

输出格式

无

输入输出样例

输入 ：

5 1
4 3 2 1 5

输出 ：

2

题目解析：

这道题一开始以为是很简单的sort直接乱杀，没想到写出来…   就对了60%的样例

第一版代码如下

#include<bits/stdc++.h>
using namespace std;
const long long N=5e7+1;
int q[N];
int main(){int n,k;cin>>n>>k;for(int i=0;i<n;i++){cin>>q[i];}sort(q,q+n);cout<<q[k]<<" ";return 0;   
} 

测试样例结果如下：