クラス分け (Class Division)
日本語
Language
Contribute a translation- Time limit
- 2000 ms
- Memory limit
- 1024 MB
- Submissions
- 0
- Correct
- 0
- Solved by
- 0
- AC rate
- —
Statement
JOI 高校の 1 年生は全部で \(N\) 人であり，\(1\) から \(N\) までの番号が付けられている．
ある日，1 年生 \(N\) 人は試験を受験した．生徒 \(i\) (\(1 \leqq i \leqq N\)) の得点は \(A_i\) 点であった．ここで，\(N\) 人全員が同じ得点を取ったわけではなかった．
この試験の成績によって来年度のクラス分けが決定される．具体的には，ある整数 \(x\) が選ばれて，得点が \(x\) 点以上の生徒は進学クラス，得点が \(x\) 点未満の生徒は普通クラスとなるように \(N\) 人の生徒が \(2\) クラスに分けられる．
ここで，それぞれのクラスには \(1\) 人以上の生徒が属するようにし，また進学クラスの生徒の数と普通クラスの生徒の数の差が最小となるような分け方が選ばれる．更に，そのような分け方が複数考えられる場合は，その中で進学クラスの人数が最小となるような分け方が選ばれる．
生徒の数とそれぞれの生徒の得点が与えられたとき，進学クラスの生徒の得点の最低点を求めるプログラムを作成せよ．
Constraints
- \(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\)．
- 入力される値はすべて整数である．
Subtasks
- (\(20\) 点) \(N = 3\)．
- (\(20\) 点) \(A_i\) は \(500, 800, 1\,000\) のいずれかである (\(1 \leqq i \leqq N\))．
- (\(20\) 点) \(A_i \neq A_j\) (\(1 \leqq i < j \leqq N\))．
- (\(40\) 点) 追加の制約はない．
Input
入力は以下の形式で与えられる．
\(N\)
\(A_1\) \(A_2\) \(\cdots\) \(A_N\)
Output
進学クラスの生徒の得点の最低点を \(1\) 行で出力せよ．
Examples
3 1000 500 800
1000
例えば，\(x = 900\) とすると，生徒 \(1\) は進学クラスに，生徒 \(2, 3\) は普通クラスに振り分けられる．
考えられるもう一つの生徒の分け方は，生徒 \(1, 3\) を進学クラスに，生徒 \(2\) を普通クラスに振り分けるものである．これは例えば \(x = 800\) とすれば実現できる．
この \(2\) つの分け方は，どちらも進学クラスの生徒の数と普通クラスの生徒の数の差は \(1\) となる．よって，進学クラスの生徒の数が最小となる分け方である前者が選ばれる．このとき，進学クラスの生徒の得点の最低点は \(1\,000\) 点である．
この入力例はすべての小課題の制約を満たす．
6 100 75 41 75 13 89
89
\(x = 89\) とすると，生徒 \(1, 6\) が進学クラスに振り分けられ，生徒 \(2, 3, 4, 5\) が普通クラスに振り分けられる．このとき進学クラスの生徒の得点の最低点は \(89\) 点である．
この入力例は小課題 \(4\) の制約を満たす．
6 20 25 12 7 13 16
16
この入力例は小課題 \(3, 4\) の制約を満たす．
8 364353982 103422534 437367896 91518637 364353982 221490368 437367896 103422534
364353982
この入力例は小課題 \(4\) の制約を満たす．
Notes
JOI 2026 · JCIOI · CC BY-SA 4.0
Tags
No tags yet