首页 > 代码库 > 第K大 [ACdream 1099] 瑶瑶的第K大
第K大 [ACdream 1099] 瑶瑶的第K大
瑶瑶的第K大
Time Limit: 10000/5000MS (Java/Others)Memory Limit: 512000/256000KB (Java/Others)
SubmitStatisticNext Problem
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
输出第 k 大的数字。
Sample Input
5 25 4 1 3 1
Sample Output
4
Hint
如2，2，1中三个数字中第一大数字为2，第二大数字也为2，第三大数字为1 。
Source
tsyao
Manager
tsyao
SubmitStatistic
这题卡时间卡得有点紧、利用快排的思想处理、加输入外挂3964ms飘过= =
/** this code is made by 123* Problem: 1099* Verdict: Accepted* Submission Date: 2014-09-25 10:59:40* Time: 3964MS* Memory: 25112KB*/#include<iostream>#include<cstring>#include<cstdio>using namespace std;#define N 6000010 int 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) //从右往左，找到第一个大于tmp的 j--; a[i]=a[j]; while(i<j && a[i]>=tmp) //从左往右，找到第一个小于tmp的 i++; a[j]=a[i]; } a[i]=tmp; if(k==i) return a[i]; else if(k<i) return 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;}
第K大 [ACdream 1099] 瑶瑶的第K大
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。