#P3405. [Usaco2009 Open]Grazing2 移动牛棚

    ID: 2596 传统题 1000ms 512MiB 尝试: 68 已通过: 38 难度: 5 上传者: 标签>难度分类普及+/提高-动态规划线性 DP贪心交换论证滚动数组CF1800Silver

[Usaco2009 Open]Grazing2 移动牛棚

[USACO 2009 Open] Grazing2 移动牛棚

题目描述

约翰有 NN 头奶牛和 SS 个排成一行的牛棚。牛棚从 11 到 SS 编号,相邻牛棚之间的距离为 11。第 ii 头奶牛起初在牛棚 PiP_i,移动到牛棚 qq 要走 ∣Pi−q∣|P_i-q| 的距离,进出牛棚本身不计距离。

约翰想让奶牛在整排牛棚中尽可能分散,同时让相邻奶牛的距离尽量一致。按原题示例所用的规则,先让最左和最右的奶牛占据 11 号和 SS 号牛棚。令

d=⌊S−1N−1⌋.d=\left\lfloor\frac{S-1}{N-1}\right\rfloor.

相邻奶牛的间距与 dd 相差至多 11,并且间距等于 dd 的相邻对要尽可能多。等价地,相邻间距只能为 dd 或 d+1d+1,其中恰有 (S−1) mod (N−1)(S-1)\bmod(N-1) 个间距为 d+1d+1。

例如,44 头奶牛和 88 个牛棚时,(1,3,5,8)(1,3,5,8) 和 (1,3,6,8)(1,3,6,8) 都符合要求,(1,2,4,7)(1,2,4,7) 和 (1,2,4,8)(1,2,4,8) 均不符合要求。求一种符合要求的安置,使所有奶牛移动的距离之和最小。

输入格式

从标准输入读入。第一行是两个整数 N,SN,S。接下来 NN 行,第 ii 行是一个整数 PiP_i。

输出格式

向标准输出输出一行一个整数,表示最小总移动距离。

5 10
2
8
1
3
9
4

样例解释

下表用 A 到 E 表示按初始位置从左到右排列的五头奶牛,· 表示空牛棚。移动总距离为 1+2+1=41+2+1=4。

牛棚 1 2 3 4 5 6 7 8 9 10
初始 A B C · · · D E ·
最终 · B C · E
移动距离 0 1 2 0 1

数据范围与约定

2≤N≤1 5002\le N\le1\,500,N≤S≤106N\le S\le10^6,1≤Pi≤S1\le P_i\le S。原题保证答案小于 10910^9。