#1742. [Usaco2005 nov]Grazing on the Run 边跑边吃草

题目描述

John养了一只叫Joseph的奶牛。一次她去放牛，来到一个非常长的一片地，上面有N块地方长了茂盛的草。我们可

以认为草地是一个数轴上的一些点。Joseph看到这些草非常兴奋，它想把它们全部吃光。于是它开始左右行走，吃

草。John和Joseph开始的时候站在p位置。Joseph的移动速度是一个单位时间一个单位距离。不幸的是，草如果长

时间不吃，就会腐败。我们定义一堆草的腐败值是从Joseph开始吃草到吃到这堆草的总时间。Joseph可不想吃太腐

败的草，它请John帮它安排一个路线，使得它吃完所有的草后，总腐败值最小。John的数学很烂，她不知道该怎样

做，你能帮她么？

输入格式

• Line 1 : Two space-separated integers: N and L. N<=1000

• Lines 2..N+1: Each line contains a single integer giving the position P of a clump (1 <= P <= 1,000,000).

输出格式

• Line 1: A single integer: the minimum total staleness Bessie can achieve while eating all the clumps.

样例

样例输入

4 10  

1  

9  

11  

19  

INPUT DETAILS:  

Four clumps: at 1, 9, 11, and 19. Bessie starts at location 10.

样例输出

44  

OUTPUT DETAILS:  

Bessie can follow this route:  

* start at position 10 at time 0  

* move to position 9, arriving at time 1  

* move to position 11, arriving at time 3  

* move to position 19, arriving at time 11  

* move to position 1, arriving at time 29  

giving her a total staleness of 1+3+11+29 = 44.  There are other routes  

with the same total staleness, but no route with a smaller one.44

数据范围与提示