QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100
统计

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

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

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

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

输入格式

第一行两个整数 $n,L$。

第二行 $n$ 个整数,第 $i$ 个整数 $p_i$ 表示第 $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\%$ 满足 $1≤n≤50000,0≤L≤50,0≤pi≤10^9$

$subtask1(15\%):n≤200,pi≤200$

$subtask2(15\%):L=0$

$subtask3(30\%):L≤5$

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

时间限制:3000ms

空间限制:512MB