瑶瑶的第K大
Time Limit:2000MS Memory Limit:128000KB 64bit IO Format:%lld & %llu 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 。
解题思路:
手打快排,方向性、目的性地选择区间分治,输入外挂优化。
#include#include #include 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 =key) low++; 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