{"problem":{"name":"[蓝桥杯青少年组国赛 2023] 月球疏散行动","description":{"content":"为了避免太阳爆发引起的灾难，人类决定给地球装上发动机，最终逃离太阳系。原计划要带着月球一起走，结果月球行星发动机发生灾难性故障，必须炸毁月球。为此，在月球上的工作人员都要疏散回地球。 月球基地有一艘太空穿梭机可以用来疏散工作人员。但是人们分散在各处，必须前往基地集合，他们到达基地的时间不等。穿梭机可以将抵达基地等待登机的工作人员先送回地球，然后再返回基地疏散下一批工作人员。 总共有 $N$ 名","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB4281"},"statements":[{"statement_type":"Markdown","content":"为了避免太阳爆发引起的灾难，人类决定给地球装上发动机，最终逃离太阳系。原计划要带着月球一起走，结果月球行星发动机发生灾难性故障，必须炸毁月球。为此，在月球上的工作人员都要疏散回地球。\n\n月球基地有一艘太空穿梭机可以用来疏散工作人员。但是人们分散在各处，必须前往基地集合，他们到达基地的时间不等。穿梭机可以将抵达基地等待登机的工作人员先送回地球，然后再返回基地疏散下一批工作人员。\n\n总共有 $N$ 名工作人员需要疏散，太空穿梭机从月球到地球往返一次花时间 $M$ 小时，第 $i$ 个人抵达基地等待登机的时刻为 $T_i$。\n\n指挥官希望所有工作人员在基地等待的时间总和最小，而且他可以任意安排穿梭机的起飞时间，假定穿梭机足够大，可以装下所有工作人员，在不计登机和下机时间等因素的情况下，最小的等候时间总和是多少？\n\n例如：$N=5$，$M=4$，1 号~5 号工作人员到达基地的时刻依次为 11、3、3、5、10，穿梭机可以在 3 时出发，先送 2 号、3 号工作人员去地球，然后于 7 时返回月球基地；此时，4 号工作人员已于 5 时到达基地，等候了 2 小时。这时让穿梭机马上送走他，然后于 11 时从地球返回基地；此时，5 号工作人员已于 10 时到达基地，等候了 1 小时；而 1 号工作人员刚好于 11 时到达基地，等候 0 小时；穿梭机于 11 时将两人送走，即完成全部疏散任务。总的等候时间 $=$ 4 号工作人员等候时间 $+$ 5 号工作人员等候时间 $=2+1=3$ 小时。无法再找到有更小等候时间总和的方案。\n\n## Input\n\n第一行输入两个正整数 $N$（$1 \\leq N \\leq 500$），$M$（$1 \\leq M \\leq 100$），以一个空格隔开，分别表示工作人员人数和穿梭机的往返时间。第二行输入 $N$ 个正整数，依次表示某个工作人员到达基地等候登机的时刻 $T_i$（$1 \\leq T_i \\leq 4000000$），相邻两数之间用一个空格隔开。\n\n## Output\n\n输出一个整数，表示所有工作人员等候时间之和的最小值（单位：小时）。\n\n[samples]\n\n## Background\n\n本题原题：[P5017 [NOIP 2018 普及组] 摆渡车](https://www.luogu.com.cn/problem/P5017)","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4281","tags":["动态规划 DP","2023","斜率优化","前缀和","蓝桥杯青少年组"],"sample_group":[["5 4\n11 3 3 5 10","3"]],"created_at":"2026-03-03 11:09:25"}}