第十一题 月球疏散行动shj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
时间限制:1 Secshj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
内存限制:128 MBshj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【题目描述】shj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
为了避免太阳爆发引起的文难，人类决定给地球装上发动机，最终逃离太阳系。原计划要带着月球起走，结果月球行星发动机发生文难性故障，必须炸毁月球。为此，在月球上的工作人员都要疏散回地球。shj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
目球基地有一艘太空穿梭机可以用来疏散工作人员。但是人们分散在各处，必须前往基地集合，他们到达基地的时间不等。穿梭机可以将抵达基地等待登机的工作人员先送回地球，然后再返回基地疏散下一批工作人员。shj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
总共有N名工作人员需要疏散，太空穿梭机从月球到地球往返一次花时间M小时，第i个人抵达基地等待登机的时刻为Ti;。shj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
指挥官希望所有工作人员在基地等待的时间总和最小，而且他可以任意安排穿梭机的起飞时间，假定穿梭机足够大，可以装下所有工作人员，在不计登机和下机时间等因素的情况下，最小的等候时间总和是多少?shj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【输入】shj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第一行输入两个正整数N (1≤N≤500) ，M (1≤M≤100) ，以一个空格隔开，分别表示工作人员人数和穿梭机的往返时间shj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第二行输入N个正整数，依次表示某个工作人员到达基地等候登机的时刻Ti(1≤Ti≤4000000) ，相邻两数之间用一个空格隔开shj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【输出】shj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出一个整数，表示所有工作人员等候时间之和的最小值 (单位: 小时)shj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例输入】shj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
5 4shj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
11 3 3 5 10shj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例输出】shj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
3shj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【提示】shj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
例如: N=5，M=4，1号~5号工作人员到达基地的时刻依次为11、3、3、5、10穿梭机可以在3时出发，先送2号、3号工作人员去地球，然后于7时返回月球基地:此时，4号工作人员已于5时到达基地，等候了2小时。这时让穿梭机马上送走他，然后于11时从地球返回基地;shj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
此时，5号工作人员已于10时到达基地，等候了1小时;shj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
而1号工作人员刚好于11时到达基地，等候0小时;shj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
穿梭机于11时将两人送走，即完成全部疏散任务。总的等候时间=4号工作人员等候时间+5号工作人员等候时间=2+1=3小时。shj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
无法再找到有更小等候时间总和的方案.shj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
shj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
