#PQJ755x4897. QOJ 755_4897

    ID: 3031 传统题 3000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2021 集训队互测双指针

QOJ 755_4897

标题: 音符大师 - Problem - QOJ.ac

#4897. 音符大师

Statistics

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

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

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

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

输入格式

第一行两个整数 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% 满足 1≤n≤50000,0≤L≤50,0≤pi≤109

请注意,第三组样例测试数据(Extra Test #3)不满足 L≤50 的限制,其 L 的值为 68。

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

subtask2(15%):L=0

subtask3(30%):L≤5

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