#2021. 音符大师

音符大师

音符大师

题目描述

标题: 音符大师 - 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%):无特殊限制。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

4 1 
6 3 7 1
9

样例 2

200 25
54 137 169 53 122 123 164 30 6 55 33 152 20 27 113 184 26 59 24 71 141 71 137 157 45 143 162 148 67 56 42 7 145 172 157 179 34 25 20 54 36 121 186 53 61 121 117 51 183 78 34 77 183 200 44 103 6 146 173 139 119 180 0 158 30 91 93 140 84 179 179 13 72 68 50 104 192 199 69 22 17 147 91 3 63 1 190 163 163 46 186 182 91 152 164 117 71 44 184 129 141 2 191 51 30 121 106 141 66 194 124 133 48 4 112 38 40 105 169 11 171 86 131 59 137 169 57 72 43 113 80 67 24 6 38 55 181 73 33 189 165 77 200 119 118 45 13 186 179 166 187 129 28 139 109 109 39 126 99 95 160 168 152 132 182 181 189 0 29 149 80 59 118 119 66 179 22 75 129 138 40 5 6 159 103 73 46 78 49 44 176 61 174 124 119 3 65 6 151 189
3288