#P3405. [Usaco2009 Open]Grazing2 移动牛棚
[Usaco2009 Open]Grazing2 移动牛棚
[USACO 2009 Open] Grazing2 移动牛棚
题目描述
约翰有 头奶牛和 个排成一行的牛棚。牛棚从 到 编号,相邻牛棚之间的距离为 。第 头奶牛起初在牛棚 ,移动到牛棚 要走 的距离,进出牛棚本身不计距离。
约翰想让奶牛在整排牛棚中尽可能分散,同时让相邻奶牛的距离尽量一致。按原题示例所用的规则,先让最左和最右的奶牛占据 号和 号牛棚。令
相邻奶牛的间距与 相差至多 ,并且间距等于 的相邻对要尽可能多。等价地,相邻间距只能为 或 ,其中恰有 个间距为 。
例如, 头奶牛和 个牛棚时, 和 都符合要求, 和 均不符合要求。求一种符合要求的安置,使所有奶牛移动的距离之和最小。
输入格式
从标准输入读入。第一行是两个整数 。接下来 行,第 行是一个整数 。
输出格式
向标准输出输出一行一个整数,表示最小总移动距离。
5 10
2
8
1
3
9
4
样例解释
下表用 A 到 E 表示按初始位置从左到右排列的五头奶牛,· 表示空牛棚。移动总距离为 。
| 牛棚 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 初始 | A | B | C | · | · | · | D | E | · | |
| 最终 | · | B | C | · | E | |||||
| 移动距离 | 0 | 1 | 2 | 0 | 1 | |||||
数据范围与约定
,,。原题保证答案小于 。