[JOI 2024 Final] 室温 / Room Temperature

Luogu
IDLGP10205
Time2000ms
Memory1024MB
DifficultyP3
贪心2024JOI(日本)
K 董事长负责调节高管们的房间的室温,他希望高管们能尽可能舒适地工作。 现在房间里有 $N$ 位高管。每位高管都有一个从 $1$ 到 $N$ 的编号。不穿外套时,高管 $i\ (1 \leq i \leq N)$ 的舒适温度是 $A_{i}$ 度。另外,每位高管每穿一件外套,舒适温度就会降低 $T$ 度。也就是说,高管 $i$ 如果穿了 $k$ 件外套,那么高管 $i$ 的舒适温度就是 $A_{i}-k T$ 度。 如果房间的温度是 $x$ 度,某位高管的舒适温度是 $y$ 度,那么这位高管的不舒适度就是 $|x-y|$。其中,$|t|$ 表示 $t$ 的绝对值。每位高管会根据房间的温度,穿上大于等于 $0$ 件合适的外套,使得不舒适度最小。 K 董事长把高管们的不舒适度的最大值称为房间的不舒适度,并决定要把房间的温度设定为使得房间的不舒适度最小的值。但是,设定的温度必须是整数。 给定高管和舒适温度的信息。编写一个程序,求出房间的不舒适度可能的最小值。 ## Input 第一行包含两个整数 $N,T$。 第二行包含用空格分隔的 $N$ 个整数 $A_1, A_2, \ldots, A_N$。 ## Output 输出一行一个整数,表示房间的不舒适度可能的最小值。 [samples] ## Note 对于所有输入数据,满足: - $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)$ 详细子任务附加限制及分值如下表所示。 |子任务| 附加限制| 分值| |:-:|:-:|:-:| |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| 无附加限制 |15|
Samples
Input #1
2 4
19 24
Output #1
1
Input #2
3 1
21 19 23
Output #2
0
Input #3
6 8
24 22 21 25 29 17
Output #3
2
API Response (JSON)
{
  "problem": {
    "name": "[JOI 2024 Final] 室温 / Room Temperature",
    "description": {
      "content": "K 董事长负责调节高管们的房间的室温,他希望高管们能尽可能舒适地工作。 现在房间里有 $N$ 位高管。每位高管都有一个从 $1$ 到 $N$ 的编号。不穿外套时,高管 $i\\ (1 \\leq i \\leq N)$ 的舒适温度是 $A_{i}$ 度。另外,每位高管每穿一件外套,舒适温度就会降低 $T$ 度。也就是说,高管 $i$ 如果穿了 $k$ 件外套,那么高管 $i$ 的舒适温度就是 $A_{",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10205"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "K 董事长负责调节高管们的房间的室温,他希望高管们能尽可能舒适地工作。\n\n现在房间里有 $N$ 位高管。每位高管都有一个从 $1$ 到 $N$ 的编号。不穿外套时,高管 $i\\ (1 \\leq i \\leq N)$ 的舒适温度是 $A_{i}$ 度。另外,每位高管每穿一件外套,舒适温度就会降低 $T$ 度。也就是说,高管 $i$ 如果穿了 $k$ 件外套,那么高管 $i$ 的舒适温度就是 $A_{...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments