第K小数

63 阅读 0 评论 42 点赞

我是靠谱客的博主心灵美老鼠，最近开发中收集的这篇文章主要介绍第K小数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

我们学校终于有自己的oj了，学长让我们每个人都出题挂在上面，最关键的还是老生常谈的问题——A题。

今日，偶见队友出了一题第k小数，果断找模板了，谁知普通的第k小数的代码最好也就只能把时间复杂度控制在O(n）。坑啊，这孩子把时间卡的太狠了，超时了好多次，最后一看标程，短短十几行代码，这让我情何以堪！这情形果断把这强大的代码深究一番，仔细一看，其实核心代码就一行：kth_element(a,a+k,a+n);

据说这强大的库函数时间复杂度是O（1）的！！！有感兴趣的，可以百度一下～

下面是题目：

1031: 不高不矮萌萌哒

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 48 Solved: 9
[ Submit][ Status][ Web Board]

Description

B区篮球场有毕业生开演唱会，DoubleQ远远的望去，那围了一群妹子，高矮不一。Double想过去凑凑热闹，看看能不能遇到他的真命天女。DoubleQ的女神应符合以下两点要求：
（1）不能太高
（2）不能太矮
在茫茫人海中，聪明的ACMer们来帮助DoubleQ快速的找到他的True Love吧！

Input

多组测试样例。第一行输入一个整数n，代表妹子的总人数，接下来n行输入，每行输入一个数m，代表妹子的身高。上天故意刁难DoubleQ，所以每个妹子的身高都扩大了好多好多倍，1 <= m <= 10^7， 1<= n <= 10^5 。

Output

输出人群中不高不矮的妹子身高，她就是DoubleQ的女神。

Sample Input

Sample Output

HINT

DoubleQ是个专一的人，所以每组测试样例只会有一个女神。

PS：其实就是求最中间的那个身高。

上具体代码：

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#define INF 0x7fffffff
using namespace std;
int a[10000005];
int main()
{
    int n,k;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        k=n/2;
        nth_element(a,a+k,a+n);
        printf("%dn",a[k]);
    }
    return 0;
}