|
试题描述
|
|
输入两个正整数N、K，以及N个整数Ai，求第K小数。
|
|
输入
|
|
第一行为两个正整数N、K。
第二行为N个正整数Ai。 |
|
输出
|
|
输出第K小数。
|
|
输入示例
|
|
5 4
1 2 3 3 5 |
|
输出示例
|
|
3
|
|
其他说明
|
|
1<=K<=N<=200000
-10^9<=Ai<=10^9 |
学了一个好用的STL，nth_element(begin,k,end)
如在A[i]--A[n]中查找k小，则先nth_element(A+1,A+k,A+n+1)，再输出A[k]即可，时间复杂度为O(N)。
#include<cstdio> #include<cctype> #include<queue> #include<cstring> #include<algorithm> #define rep(s,t) for(int i=s;i<=t;i++) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘; return x*f; } const int maxn=2000010; int A[maxn]; int main() { int n=read(),k=read(); rep(1,n) A[i]=read(); nth_element(A+1,A+k,A+n+1); printf("%d\n",A[k]); return 0; }
原文：http://www.cnblogs.com/wzj-is-a-juruo/p/4618090.html
