/ WHOJ / 题库 /

[NOIP2018 普及组] 摆渡车

[NOIP2018 普及组] 摆渡车

题目描述

有 \(n\) 名同学要乘坐摆渡车从人大附中前往人民大学,第 \(i\) 位同学在第 \(t_i\) 分钟去 等车。只有一辆摆渡车在工作,但摆渡车容量可以视为无限大。摆渡车从人大附中出发、 把车上的同学送到人民大学、再回到人大附中(去接其他同学),这样往返一趟总共花费 \(m\) 分钟(同学上下车时间忽略不计)。摆渡车要将所有同学都送到人民大学。

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

注意:摆渡车回到人大附中后可以即刻出发。

格式

输入格式

第一行包含两个正整数 \(n, m\),以一个空格分开,分别代表等车人数和摆渡车往返一趟的时间。

第二行包含 \(n\) 个正整数,相邻两数之间以一个空格分隔,第 \(i\) 个非负整数 \(t_i\) 代表第 \(i\) 个同学到达车站的时刻。

输出格式

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

样例1

样例输入1

5 1 
3 4 4 3 5

样例输出1

0

样例2

样例输入2

5 5 
11 13 1 5 5

样例输出2

4

样例1解释

同学 \(1\) 和同学 \(4\) 在第 \(3\) 分钟开始等车,等待 \(0\) 分钟,在第 \(3\) 分钟乘坐摆渡车出发。摆渡车在第 \(4\) 分钟回到人大附中。

同学 \(2\) 和同学 \(3\) 在第 \(4\) 分钟开始等车,等待 \(0\) 分钟,在第 \(4\) 分钟乘坐摆渡车 出发。摆渡车在第 \(5\) 分钟回到人大附中。

同学 \(5\) 在第 \(5\) 分钟开始等车,等待 \(0\) 分钟,在第 \(5\) 分钟乘坐摆渡车出发。自此 所有同学都被送到人民大学。总等待时间为 \(0\)。

样例2解释

同学 \(3\) 在第 \(1\) 分钟开始等车,等待 \(0\) 分钟,在第 \(1\) 分钟乘坐摆渡车出发。摆渡 车在第 \(6\) 分钟回到人大附中。

同学 \(4\) 和同学 \(5\) 在第 \(5\) 分钟开始等车,等待 \(1\) 分钟,在第 \(6\) 分钟乘坐摆渡车 出发。摆渡车在第 \(11\) 分钟回到人大附中。

同学 \(1\) 在第 \(11\) 分钟开始等车,等待 \(2\) 分钟;同学 \(2\) 在第 \(13\) 分钟开始等车, 等待 \(0\) 分钟。他/她们在第 \(13\) 分钟乘坐摆渡车出发。自此所有同学都被送到人民大学。 总等待时间为 \(4\)。

可以证明,没有总等待时间小于 \(4\) 的方案。

限制

对于 \(10\%\) 的数据,\(n ≤ 10, m = 1, 0 ≤ t_i ≤ 100\)。

对于 \(30\%\) 的数据,\(n ≤ 20, m ≤ 2, 0 ≤ t_i ≤ 100\)。

对于 \(50\%\) 的数据,\(n ≤ 500, m ≤ 100, 0 ≤ t_i ≤ 10^4\)。

另有 \(20\%\) 的数据,\(n ≤ 500, m ≤ 10, 0 ≤ t_i ≤ 4 \times 10^6\)。

对于 \(100\%\) 的数据,\(n ≤ 500, m ≤ 100, 0 ≤ t_i ≤ 4 \times 10^6\)。