P10205 [JOI 2024 Final] Room Temperature / Room Temperature

Chairman K is responsible for adjusting the room temperature for the executives. He wants them to work as comfortably as possible. There are $N$ executives in the room. Each executive is assigned an ID from $1$ to $N$. Without wearing a coat, executive $i\ (1 \leq i \leq N)$ has a comfortable temperature of $A_i$ degrees. Also, for each coat an executive wears, their comfortable temperature decreases by $T$ degrees. That is, if executive $i$ wears $k$ coats, then executive $i$'s comfortable temperature becomes $A_i - kT$ degrees. If the room temperature is $x$ degrees and an executive's comfortable temperature is $y$ degrees, then this executive's discomfort is $|x - y|$, where $|t|$ denotes the absolute value of $t$. Each executive will, depending on the room temperature, wear an appropriate number of coats $k \geq 0$ to minimize their discomfort. Chairman K defines the maximum discomfort among all executives as the room's discomfort, and he decides to set the room temperature to a value that minimizes the room's discomfort. However, the chosen temperature must be an integer. Given the information about the executives and their comfortable temperatures, write a program to find the minimum possible value of the room's discomfort.

The first line contains two integers $N, T$. The second line contains $N$ integers $A_1, A_2, \ldots, A_N$ separated by spaces.

Output one integer on a single line, representing the minimum possible value of the room's discomfort.

For all input data, the following constraints hold: - $2 \leq N \leq 5\times 10^5$ - $1 \leq T \leq 10^{9}$ - $1 \leq A_i \leq 10^{9}(1 \leq i \leq N)$ The detailed additional constraints and scores for each subtask are shown in the table below. |Subtask|Additional Constraints|Score| |:-:|:-:|:-:| |1|$N=2$|15| |2|$N \leq 3000, T=1$|5| |3|$N \leq 3000, T \leq 2$|30| |4|$N \leq 3000, T \leq 3000$|35| |5|No additional constraints|15| Translated by ChatGPT 5