[ACdream 1099] 瑶瑶的第K大

瑶瑶的第K大

Problem Description

一天，萌萌的妹子--瑶瑶(tsyao)很无聊，就来找你玩。可是你们都不知道玩什么。。。尴尬了一阵子，机智的瑶瑶就提议：“这样吧，你说N个整数xi，然后在随意说一个数字k，我能够快速地说出这些数字里面第 k 大的数字。”

Input

第1行 两个整数N, K以空格隔开；

第2行 有N个整数（可出现相同数字，均为随机生成），同样以空格隔开。

0 < n ≤ 5*10^6 , 0 < k ≤ n

1 ≤ xi ≤ 10^8

Output

Sample Input

5 2
5 4 1 3 1

Sample Output

4

Hint

#include
#include
#include
using namespace std;
#define N 6000010int n,k;
int a[N];int input()
{int ans=0;char a;while((a=getchar())<'0'||a>'9');ans=a-'0';while((a=getchar())>='0'&&a<='9'){ans=ans*10+a-'0';}return ans;
}
int qsort(int s,int t)
{int i=s,j=t,tmp;if(s<t){tmp=a[s];while(i!=j){while(j>i && a[j]<=tmp) j--;a[i]=a[j];while(i=tmp) i++;a[j]=a[i];}a[i]=tmp;if(k==i) return a[i];else if(kreturn qsort(s,i-1);else return qsort(i+1,t);}
}
int main()
{n=input();k=input();for(int i=1;i<=n;i++)a[i]=input();printf("%d\n",qsort(1,n));return 0;
}

转载于:https://www.cnblogs.com/hate13/p/4040497.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！