← 返回题目列表

AtCoder · joi2026_yo2_a

A. 班级划分

中文机器翻译题面 查看原题

配点: 100 点

問題文

JOI高中所有一年级学生 N 是一个人, 它们的编号最大为1 从 N 。

有一天,一年级学生 N 此人参加了考试。学生 i (1 \leqq i \leqq N) 的分数是 A_i 点。在这里,N 并非每个人都得到相同的分数。

明年的班级安排将根据本次考试的结果确定。具体来说,一些整数 选择 x ,得分为 x 积分或以上的学生预备班,得分为 x 学生少于普通班以便 N 学生 2 它分为类。

这里,每个班级都有 1 选择划分方法,使一个以上的学生属于一个班级,并将高级班的学生人数与普通班的学生人数之间的差异最小化。此外,如果可以有多个这样的班级,则选择使预科班学生人数最少的一个。

给定学生人数和每个学生的分数,编写一个程序找出预科班学生的最低分数。

制約

  • 2 \leqq N \leqq 500\,000.
  • 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N).
  • 是 i, j (1 \leqq i < j \leqq N) 存在 是 A_i \neq A_j.
  • 所有输入值都是整数。

小課題

  1. (20 点) N = 3.
  2. (20 点) A_i 表示 500, 800, 1\,000 (1 \leqq i \leqq N).
  3. (20 点) A_i \neq A_j (1 \leqq i < j \leqq N).
  4. (40 点)没有额外的限制。

入力

输入按以下格式给出。

N
A_1 A_2 \cdots A_N

出力

预科班学生成绩最低 1 行。


入力例 1

3
1000 500 800

出力例 1

1000

例如,x = 900 然后学生 1 是预科班的学生。 2, 3 被分配到普通班级。

划分学生的另一种可能方法是 1, 3 致预科班同学们 2 分为普通班。这是例如 这可以通过 x = 800 来实现。

这个 2 两种情况下,预科班学生人数与普通班学生人数之差为 1 变为。因此,选择前一种方式,因为这样可以最大限度地减少预科班的学生人数。此时,预科班学生的最低成绩是 1\,000 点。

此输入示例满足所有子任务约束。


入力例 2

6
100 75 41 75 13 89

出力例 2

89

x = 89 然后学生 1, 6 被分配到预科班,学生 2, 3, 4, 5 被分配到普通班级。此时,预科班学生的最低成绩是 89 点。

此输入示例是一个小作业。 4 满足约束。


入力例 3

6
20 25 12 7 13 16

出力例 3

16

此输入示例是一个小作业。 3, 4 满足约束。


入力例 4

8
364353982 103422534 437367896 91518637 364353982 221490368 437367896 103422534

出力例 4

364353982

此输入示例是一个小作业。 4 满足约束。