ACdream 1099——瑶瑶的第K大——————【快排舍半，输入外挂】

瑶瑶的第K大

Time Limit:2000MS Memory Limit:128000KB 64bit IO Format:%lld & %llu

Submit Status Practice ACdream 1099

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

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;

}

巴特西

ACdream 1099——瑶瑶的第K大——————【快排舍半，输入外挂】

最新文章

热门文章