室温 (Room Temperature)
日本語
Language
Contribute a translation- Time limit
- 2000 ms
- Memory limit
- 1024 MB
- Submissions
- 0
- Correct
- 0
- Solved by
- 0
- AC rate
- —
Statement
K 理事長は，役員がいる部屋の室温を調節する役割を担っており，役員ができるだけ快適に過ごせるようにしたいと考えている．
今，部屋に \(N\) 人の役員がいる．それぞれの役員には \(1\) から \(N\) までの番号が付けられており，上着を着ていない状態での役員 \(i\) (\(1 \leqq i \leqq N\)) の適温は \(A_i\) 度である． また，それぞれの役員について，上着を \(1\) 枚着るごとに適温が \(T\) 度下がる．すなわち，役員 \(i\) が上着を \(k\) 枚着ると，役員 \(i\) の適温は \(A_i-kT\) 度になる．
室温を \(x\) 度，ある役員の適温を \(y\) 度とすると，その役員の不快度は \(|x-y|\) で表される．ただし， \(|t|\) は \(t\) の絶対値を表す．各役員は室温に応じて，不快度が最小となるよう \(0\) 枚以上の適切な枚数の上着を着る．
ここで K 理事長は，役員の不快度の最大値を部屋の不快度と呼ぶことにし，部屋の不快度が最小となるように室温を設定することにした．ただし，設定する室温は整数でなければならない．
役員と適温に関する情報が与えられたとき，部屋の不快度としてありうる最小値を求めるプログラムを作成せよ．
Input
入力は以下の形式で標準入力から与えられる．
\(N\) \(T\)
\(A_1\) \(A_2\) \(\cdots\) \(A_N\)
Output
標準出力に，部屋の不快度としてありうる最小値を \(1\) 行で出力せよ．
Constraints
- \(2 \leqq N \leqq 500\,000\)．
- \(1 \leqq T \leqq 10^9\)．
- \(1 \leqq A_i \leqq 10^9\) (\(1 \leqq i \leqq N\))．
- 入力される値はすべて整数である．
Subtasks
- (\(15\) 点) \(N = 2\)．
- (\(5\) 点) \(N \leqq 3\,000\)，\(T = 1\)．
- (\(30\) 点) \(N \leqq 3\,000\)，\(T \leqq 2\)．
- (\(35\) 点) \(N \leqq 3\,000\)，\(T \leqq 3\,000\)．
- (\(15\) 点) 追加の制約はない．
Examples
2 4 19 24
1
たとえば，室温を \(16\) 度に設定すると，役員 \(1\) は上着を \(1\) 枚着ることで適温が \(15\) 度になり，役員 \(1\) の不快度は \(|16 - 15| = 1\) となる． 役員 \(2\) は上着を \(2\) 枚着ることで適温が \(16\) 度になり，役員 \(2\) の不快度は \(|16 - 16| = 0\) となる．
このとき，部屋の不快度は \(1\) となる． また，部屋の不快度を \(1\) より小さくすることはできないので， \(1\) を出力する．
この入力例は小課題 \(1, 4, 5\) の制約を満たす．
3 1 21 19 23
0
たとえば，室温を \(19\) 度に設定すると，部屋の不快度は \(0\) となる．よって \(0\) を出力する．
この入力例は小課題 \(2, 3, 4, 5\) の制約を満たす．
6 8 24 22 21 25 29 17
2
たとえば，室温を \(15\) 度に設定すると，部屋の不快度は \(2\) となる．部屋の不快度を \(2\) より小さくすることはできないので \(2\) を出力する．
この入力例は小課題 \(4, 5\) の制約を満たす．
Notes
JOI 2024 · JCIOI · CC BY-SA 4.0
Tags
No tags yet