문제
정올 캠프에 N명의 학생들이 참가하였다. 최적의 환경을 위해, 원장님은 강의실 온도를 조절하고 있다.
각 학생들마다 요구하는 적정 온도는 다 다르다. 이 상태에서 한 학생이 외투 한 벌을 입을 때마다, 학생이 요구하는 적정 온도는 T 만큼 떨어진다.
원장님이 방 온도를 설정하면, 각 학생들은 그 방 온도에 최대한 근접하도록 외투를 알아서 갖다가 입는다.
외투를 적절히 입은 학생의 적정 온도와 방 온도의 차이(절댓값)을 그 학생의 "불편도"라고 하자.
예를 들어, 방 온도가 14도, T = 5, 상윤이의 적정 온도가 27도, 시윤이의 적정 온도가 60도라 하자.
상윤이는 방 온도인 14도에 최대한 근접하기 위해 외투를 3벌 입어서 자신의 적정 온도를 27 - 5 x 3 = 12도로 바꿀 것이다.
시윤이는 방 온도인 14도에 최대한 근접하기 위해 외투를 9벌 입어서 자신의 적정 온도를 60 - 5 x 9 = 15도로 바꿀 것이다.
따라서 방 온도가 14도라면 상윤이의 불편도는 14 - 12 = 2, 시윤이의 불편도는 15 - 14 = 1 이 된다.
방 온도가 설정됐을 때, 모든 N명의 학생들의 불편도 중 최댓값을 "캠프 불편도"라고 하자.
원장님의 목표는 "캠프 불편도"를 최소로 만드는 것이다.
"캠프 불편도"의 최솟값을 출력하자.
입력
첫 줄에 학생 수 N 과, 외투를 한 벌 입을 때마다 감소하는 적정 온도 T 가 입력된다.
두 번째 줄에는 각 학생들의 적정 온도가 N 개의 정수로 입력된다.
2 ≤ N ≤ 500,000
1 ≤ T ≤ 109
1 ≤ 각 학생들의 적정 온도 ≤ 109
출력
첫 줄에, "캠프 불편도" 의 최솟값을 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 15점 | N = 2 |
| #2 | 5점 | N ≤ 3000, T = 1 |
| #3 | 30점 | N ≤ 3000, T ≤ 2 |
| #4 | 35점 | N ≤ 3000, T ≤ 3000 |
| #5 | 15점 | 제약 조건 없음 |
예제1
510
21321062650
3
원장님은 방 온도를 19도로 맞춰 놓으면 된다.
첫 번째 학생은 외투를 입지 않고, 불편도가 2 이다.
두 번째 학생은 외투를 1벌 입고, 불편도가 3 이다.
세 번째 학생은 외투를 9벌 입고, 불편도가 3 이다.
네 번째 학생은 외투를 1벌 입고, 불편도가 3 이다.
다섯 번째 학생은 외투를 3벌 입고, 불편도가 1 이다.
따라서 캠프 불편도는 3이 되고, 이것이 최소다.
( 꼭 19도일 필요는 없다. 방 온도를 9도로 맞춰도 캠프 불편도는 3이 된다. )