洛谷P1923 【深基9.例4】求第 k 小的数

P1923 【深基9.例4】求第 k 小的数

题目描述

输入 $n$（$1\le n<5000000$ 且 $n$ 为奇数）个数字 $a_i$（$1\le a_i<{10}^9$），输出这些数字的第 $k$ 小的数。最小的数是第 $0$ 小。

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

输入格式

第一行有两个整数，分别表示 $n$ 和 $k$。

第二行有 $n$ 个整数，第 $i$ 个数表示 $a_i$。

输出格式

一个整数，表示第 $k$ 小的数。

输入输出样例 #1

输入 #1

5 1
4 3 2 1 5

输出 #1

2

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int n,k;
int main()
{scanf("%d%d",&n,&k);int tmp;vector<int> a;for(int i=1;i<=n;++i){scanf("%d",&tmp);a.push_back(tmp);}nth_element(a.begin(),a.begin()+k,a.end());printf("%d",a[k]);return 0;
}

非常的直接