luogu#P5017. [NOIP2018 普及组] 摆渡车

    ID: 9041 远端评测题 2000ms 256MiB 尝试: 18 已通过: 6 难度: 5 上传者: 标签>动态规划dp2018NOIp 普及组枚举暴力深度优先搜索DFS斜率优化

[NOIP2018 普及组] 摆渡车

题目背景

NOIP2018 普及组 T3

题目描述

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

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

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

输入格式

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

输出格式

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

5 1 
3 4 4 3 5 
0
5 5 
11 13 1 5 5 
4

提示

样例 1 说明

同学 11 和同学 44 在第 33 分钟开始等车,等待 00 分钟,在第 33 分钟乘坐摆渡车出发。摆渡车在第 44 分钟回到人大附中。
同学 22 和同学 33 在第 44 分钟开始等车,等待 00 分钟,在第 44 分钟乘坐摆渡车 出发。摆渡车在第 55 分钟回到人大附中。
同学 55 在第 55 分钟开始等车,等待 00 分钟,在第 55 分钟乘坐摆渡车出发。自此 所有同学都被送到人民大学。总等待时间为 00

样例 2 说明

同学 33 在第 11 分钟开始等车,等待 00 分钟,在第 11 分钟乘坐摆渡车出发。摆渡 车在第 66 分钟回到人大附中。
同学 44 和同学 55 在第 55 分钟开始等车,等待 11 分钟,在第 66 分钟乘坐摆渡车 出发。摆渡车在第 1111 分钟回到人大附中。
同学 11 在第 1111 分钟开始等车,等待 22 分钟;同学 22 在第 1313 分钟开始等车, 等待 00 分钟。他/她们在第 1313 分钟乘坐摆渡车出发。自此所有同学都被送到人民大学。 总等待时间为 44
可以证明,没有总等待时间小于 44 的方案。

数据规模与约定

对于 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