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 2 5 4 1 3 1
Sample Output
4
Hint
如2，2，1中三个数字中第一大数字为2，第二大数字也为2，第三大数字为1 。
解题思路：
手打快排，方向性、目的性地选择区间分治，输入外挂优化。
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn=1e7;
int a[maxn];
int scan(){char c;int sgn,ret;if(c=getchar(),c==EOF)return 0;while(c!='-'&&(c<'0'||c>'9'))c=getchar();sgn=(c=='-')?-1:1;ret=(c=='-')?0:(c-'0');while(c=getchar(),c>='0'&&c<='9')ret=ret*10+(c-'0');ret *=sgn;return ret;
}
int mysort(int L,int R,int k){if(L==R){ //区间内只有一个值，即为所求第k大值return a[L];}int key=a[L];int low=L;int high=R;while(low<high){while(low<high&&a[high]<=key)high--;if(low<high)a[low++]=a[high];while(low<high&&a[low]>=key)low++;if(low<high)a[high--]=a[low];}a[low]=key;if(low==k) //该基准值即为第k大的元素return a[low];else if(low>k)return mysort(L,low-1,k); //舍半逼近else return mysort(low+1,R,k);
}
int main(){int n , k;scanf("%d%d",&n,&k);for(int i=0;i<n;i++){a[i]=scan();}int ans=mysort(0,n-1,k-1);printf("%d\n",ans);return 0;
}
