#1468. CSP-模拟赛006-T3

CSP-模拟赛006-T3

题目描述

nn 名同学要乘坐小白从0101少儿编程俱乐部前往台江万达,第 ii 位同学在第 tit_i 分钟去 等车。只有一辆小白在可以运营,但小白容量可以视为无限大。小白从0101少儿编程俱乐部出发、 把车上的同学送到台江万达、再回到0101少儿编程俱乐部(去接其他同学),这样往返一趟总共花费 mm 分钟(同学上下车时间忽略不计)。摆渡车要将所有同学都送到台江万达。

小言很好奇,如果他能任意安排小白出发的时间,那么这些同学的等车时间之和最小为多少呢?

注意:小白回到0101少儿编程俱乐部后可以即刻出发。

输入格式

第一行包含两个正整数 n,mn, m,以一个空格分开,分别代表等车人数和小白往返一趟的时间。 第二行包含 nn 个正整数,相邻两数之间以一个空格分隔,第 ii 个非负整数 tit_i 代表第 ii 个同学到达车站的时刻。

输出格式

输出一行,一个整数,表示所有同学等车时间之和的最小值(单位:分钟)。

样例 #1

样例输入 #1

5 1 
3 4 4 3 5

样例输出 #1

0

样例 #2

样例输入 #2

5 5 
11 13 1 5 5

样例输出 #2

4

提示

样例 1 说明

同学 11 和同学 44 在第 33 分钟开始等车,等待 00 分钟,在第 33 分钟乘坐小白出发。小白在第 44 分钟回到0101少儿编程俱乐部。 同学 22 和同学 33 在第 44 分钟开始等车,等待 00 分钟,在第 44 分钟乘坐小白 出发。小白在第 55 分钟回到0101少儿编程俱乐部。 同学 55 在第 55 分钟开始等车,等待 00 分钟,在第 55 分钟乘坐小白出发。自此 所有同学都被送到台江万达。总等待时间为 00

数据规模与约定

对于 10%10\% 的数据,n10n ≤ 10m=1m = 10ti1000 ≤ t_i ≤ 100

对于 30%30\% 的数据,n20n ≤ 20m2m ≤ 20ti1000 ≤ t_i ≤ 100

对于 50%50\% 的数据,n500n ≤ 500m100m ≤ 1000ti1040 ≤ t_i ≤ 10^4

另有 20%20\% 的数据,n500n ≤ 500m10m ≤ 100ti4×1060 ≤ t_i ≤ 4 \times 10^6

对于 100%100\% 的数据,n500n ≤ 500m100m ≤ 1000ti4×1060 ≤ t_i ≤ 4 \times 10^6