瑶瑶的第K大
Time Limit:4000/2000MS (Java/Others)Memory Limit:256000/128000KB (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
读入要优化，否则TLE
1:STL函数实现
2：快排思想实现
#include <bits/stdc++.h>#define N 6000010int a[N];int n,k;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 solve(int l, int r){if(l == r) return a[l];int i = l, j = r, temp = a[l];if(l < r){while(i < j){while(i < j && a[j] < temp) j–;if(i < j) a[i++] = a[j];while(i < j && a[i] > temp) i++;if(i < j) a[j–] = a[i];}a[i] = temp;if(i == k) return a[i];else if(i < k) solve(i+1,r);else solve(l,i-1);}}int main(){#ifdef xxzfreopen("in.txt","r",stdin);#endif // xxzn = input();k = input();for(int i = 1; i <= n; i++) a[i] = input();printf("%d\n",solve(1,n));return 0;}利用STL实现
#include<iostream>#include <algorithm>#include<cstring>#include<cstdlib>#include<queue>#include<cstdio>using namespace std;const int N = 11111111; void scan_d(int &ret){char c;ret = 0;while((c=getchar())<'0' || c>'9');while(c>='0'&&c<='9') ret = ret*10 +(c-'0'),c=getchar();}int a[N];int main(){int n,k;cin>>n>>k;for(int i = 0 ; i<n;i++){scan_d(a[i]);}nth_element(a,a+n-k,a+n);cout<<a[n-k]<<endl;}
，生命太过短暂，今天放弃了明天不一定能得到
