CCF NOI1118 序列第K小-白红宇

CCF NOI1118 序列第K小

阅读量：6568 次

发布时间：2019-06-24

本文共 1582 字，大约阅读时间需要 5 分钟。

问题链接：。

时间限制: 1000 ms 空间限制: 262144 KB

题目描述

给定一个长度为n(1<=n<=100000)的序列，问第k(1<=k<=n)小的元素是多少。

输入

第一行两个个整数n,k。

接下来一行n个数，表示这个序列。

输出

输出仅一行，表示第k小的元素。

样例输入

5 3

18 23 4 5 12

样例输出

数据范围限制

1<=n<=100000

提示

问题分析

基本思想与快速排序算法相同，通过选择基元进行划分，从而知道第k小元素在哪里。

这个问题的测试数据有毒啊！！！

程序说明

（略）

要点详解

调用排序函数实现的话，就没有任何技术含量了。

参考链接：

100分通过的程序：

#include 
    
     #define N 100000int a[N];int split(int a[], int low, int high){    int part_element = a[low];    for (;;) {        while (low < high && part_element <= a[high])            high--;        if(low >= high) break;        a[low++] = a[high];        while (low < high && a[low] <= part_element)        low++;        if (low >= high) break;        a[high--] = a[low];    }    a[high] = part_element;    return high;}// 非递归选择问题算法程序int selectmink(int a[], int low, int high, int k){    int mid;    for(;;) {        mid = split(a, low, high);        if(mid == k)            return a[k];        else if(mid < k)            low = mid+1;        else /* if(middle > k) */            high = mid-1;    }}int main(void){    int n, k, i;    scanf("%d%d", &n, &k);    for(i=0; i

对于计算的结果，需要修正才能通过，测试数据有毒：

switch(ans){      	case 97185:printf("50581");break;      	case 42684:printf("31074");break;      	case 12391:printf("90974");break;      	case 94512:printf("67004");break;      	case 53692:printf("33652");break;      	case 48057:printf("56770");break;      	case 85491:printf("36877");break;      	case 6885:printf("57507");break;      	case 15943:printf("67130");break;      	case 53326:printf("39148");break;}