← 返回题目列表

AtCoder · joi2024ho_a

A. 室温

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

配点: 100 点

問題文

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 计算该官员的不适程度的最大值。房间不适程度 我决定将其命名为并设置室温以尽量减少房间的不适程度。但是,您设置的室温必须是整数。

给定有关执行人员和适当温度的信息,编写一个程序来找到房间的最小可能的不适程度。


入力

输入是按以下格式从标准输入给出的。

N T
A_1 A_2 \cdots A_N

出力

房间不适级别的最小可能值被输出到标准输出。 1 行上。


制約

  • 2 \leqq N \leqq 500\,000.
  • 1 \leqq T \leqq 10^9.
  • 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N).
  • 所有输入值均为整数。

小課題

  1. (15 点) N = 2.
  2. (5 点) N \leqq 3\,000,T = 1.
  3. (30 点) N \leqq 3\,000,T \leqq 2.
  4. (35 点) N \leqq 3\,000,T \leqq 3\,000.
  5. (15 点)没有额外的限制。

入力例 1

2 4
19 24

出力例 1

1

例如,如果室温 16 当设置为 1 穿一件夹克 1 穿着这些层可以让您保持适当的温度。 15 学位,军官 1 的不适程度是 |16 - 15| = 1 变为。 官员 2 穿一件夹克 2 穿着这些层可以让您保持适当的温度。 16 学位,军官 2 的不适程度是 |16 - 16| = 0 变为。

此时房间的不适程度为 1 变为。 另外,房间的不适程度 它不能小于 1 ,所以 1 。

此输入示例是一个小作业。 1, 4, 5 满足约束。 如果设置为


入力例 2

3 1
21 19 23

出力例 2

0

例如,如果室温 19 度,房间的不适程度将为 0 变为。因此 0 。

此输入示例是一个小作业。 2, 3, 4, 5 满足约束。 如果设置为


入力例 3

6 8
24 22 21 25 29 17

出力例 3

2

例如,如果室温 15 度,房间的不适程度将为 2 变为。房间的不适程度 2 不能小于 2 。

此输入示例是一个小作业。 4, 5 满足约束。 如果设置为