题目名称 3975. 图书馆
输入输出 library.in/out
难度等级 ★☆
时间限制 1000 ms (1 s)
内存限制 512 MiB
测试数据 10
题目来源 Gravatarsyzhaoss 于2024-05-25加入
开放分组 全部用户
提交状态
分类标签
思维
分享题解
通过:13, 提交:31, 通过率:41.94%
Gravatar喵喵喵 100 0.009 s 1.22 MiB C++
Gravatar喵喵喵 100 0.011 s 2.86 MiB C++
Gravatar喵喵喵 100 0.016 s 2.45 MiB C++
Gravatardustsans 100 0.020 s 3.60 MiB C++
Gravatar喵喵喵 100 0.022 s 1.82 MiB C++
Gravatar喵喵喵 100 0.024 s 5.73 MiB C++
Gravatarchenbp 100 0.106 s 1.76 MiB C++
GravatarAeeE5x 100 0.140 s 3.67 MiB C++
Gravatar花火 100 0.155 s 3.67 MiB C++
Gravatarsyzhaoss 100 0.164 s 3.67 MiB C++
关于 图书馆 的近10条评论(全部评论)

3975. 图书馆

★☆   输入文件:library.in   输出文件:library.out   简单对比
时间限制:1 s   内存限制:512 MiB

【题目背景】

为了满足市民的阅读需求,C市准备建立一个人性化的图书馆。

【题目描述】

图书馆的书架高度对于读者来说非常重要,每个人都有自己舒适的阅读高度,图书馆希望尽量为读者提供舒适的阅读环境,因此他们计划安装多个不同高度的书架,以满足大多数读者的高度需求。

但图书馆当前面临一个挑战:他们既想满足超过一半的读者的高度需求,又想让书架的高度变化范围尽可能小(最大高度与最小高度的差值尽可能的小),以保持图书馆环境的统一性和协调性。

为了解决这个问题,图书馆决定先收集 $N$ 个读者的阅读高度偏好,并将高度按照从小到大的顺序进行排列完毕。现在,请你帮助图书馆计算满足条件的最小书架高度差是多少。

【输入格式】

第 $1$ 行 :  一个整数 $N$ ,代表读者的个数。

第 $2 \sim N+1$ 行 :  一个整数 $a_i$,表示第 $i$ 个读者舒适的阅读高度。

【输出格式】

一行,最高的书架和最低的书架之间的高度差。

【样例1输入】

3
2
3
18

【样例1输出】

1

【样例2输入】

5
8
9
10
10
10

【样例2输出】

0

【样例说明】

对于样例 $1$:需要满足至少 $2$ 个读者的阅读高度,考虑书架的高度为:$2、3$,高度差为 $1$ 。

对于样例 $2$:需要满足至少 $3$ 个读者的阅读高度,考虑书架的高度为:$10$,高度差为 $0$ 。

【数据规模与约定】

对于 $100\%$ 的测试数据,$3 \leq N \leq 100000$ , $1 \leq a_i \leq 10^7$。

【来源】

2024年校际联合邀请赛 语法组-第2场 Task4