{"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_{i}-k T$ 度。\n\n如果房间的温度是 $x$ 度，某位高管的舒适温度是 $y$ 度，那么这位高管的不舒适度就是 $|x-y|$。其中，$|t|$ 表示 $t$ 的绝对值。每位高管会根据房间的温度，穿上大于等于 $0$ 件合适的外套，使得不舒适度最小。\n\nK 董事长把高管们的不舒适度的最大值称为房间的不舒适度，并决定要把房间的温度设定为使得房间的不舒适度最小的值。但是，设定的温度必须是整数。\n\n给定高管和舒适温度的信息。编写一个程序，求出房间的不舒适度可能的最小值。\n\n## Input\n\n第一行包含两个整数 $N,T$。\n\n第二行包含用空格分隔的 $N$ 个整数 $A_1, A_2, \\ldots, A_N$。\n\n## Output\n\n输出一行一个整数，表示房间的不舒适度可能的最小值。\n\n[samples]\n\n## Note\n\n对于所有输入数据，满足：\n\n- $2 \\leq N \\leq 5\\times 10^5$\n- $1 \\leq T \\leq 10^{9}$\n- $1 \\leq A_{i} \\leq 10^{9}(1 \\leq i \\leq N)$\n\n详细子任务附加限制及分值如下表所示。\n\n|子任务|\t附加限制|\t分值|\n|:-:|:-:|:-:|\n|1|\t$N=2$|\t15|\n|2|\t$N \\leq 3000, T=1$|\t5|\n|3|\t$N \\leq 3000, T \\leq 2$|\t30|\n|4|\t$N \\leq 3000, T \\leq 3000$|\t35|\n|5|\t无附加限制\t|15|","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10205","tags":["贪心","2024","JOI（日本）"],"sample_group":[["2 4\n19 24","1"],["3 1\n21 19 23","0"],["6 8\n24 22 21 25 29 17","2"]],"created_at":"2026-03-03 11:09:25"}}