QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100
[0]

# 4897. 音符大师

Statistics

你在打音游,这一关有 n 个音符,会从屏幕的最上方落下,你需要在屏幕最下方的线上打到这些音符。

判定线可以看作数轴的正半轴,n 个音符依次落下,第 i 个音符会落到 pi 的位置。你的两只手可以分别覆盖两个长度为 L 的区间,准确来说,一只手可以覆盖 [x,x+L],使得当音符落在这个区间(包括端点)的时候可以准确打到。

游戏开始时你的两只手覆盖了 [0,L],在接下来的 n 个音符落下的间隙中,你可以将你的手任意移动,移动的时间忽略不计,从 [x,x+L] 移动到 [y,y+L] 需要耗费 |xy| 的体力。

游戏开始前,你想要知道最少耗费多少体力可以依次打到所有的音符。

输入格式

第一行两个整数 n,L

第二行 n 个整数,第 i 个整数 pi 表示第 i 个音符的位置。

输出格式

一行一个整数表示最少耗费的体力。

样例输入 1

4 1 
6 3 7 1

样例输出 1

9

样例解释

两只手的移动分别是:[0,1][5,6][6,7][0,1][2,3][1,2],花费体力 6+3=9

样例输入 2/3

见下发文件 ex_game2/3.in

样例输出2/3

见下发文件 ex_game2/3.out

数据范围

对于 100% 满足 1n50000,0L50,0pi109

subtask1(15%):n200,pi200

subtask2(15%):L=0

subtask3(30%):L5

subtask4(40%):无特殊限制。

时间限制:3000ms

空间限制:512MB