P2954 [USACO09OPEN] Grazing2 S

农夫约翰有 $N$ 头奶牛$（2≤N≤1,500）$，它们被编号为 $1$ 到 $N$。他新建的谷仓有一排 $S$ 个牛栏$（N≤S≤10 ^6$ ），这些牛栏也被编号为 $1$ 到$ S$。每个牛栏与其相邻的牛栏相距为 $1$。 奶牛们已经找到了各自的牛栏准备休息，第 $i$ 头奶牛在第 $P _i$ 个牛栏里。由于奶牛们不合群，如果它们所处的牛栏彼此非常接近，它们就会变得脾气暴躁，所以农夫约翰希望将奶牛尽可能地分散开来。 约翰想要确保相邻奶牛之间的 $N−1$ 个距离尽可能大，并且希望这些距离的差值尽可能小（即接近等距）。 具体来说，约翰希望所有相邻奶牛之间的距离与 $d=\left\lfloor \dfrac{S-1}{N-1} \right\rfloor$的差值不超过 $1$。而且，他希望尽可能多的距离能够精确地等于 $d$。因此，如果有 $4$ 头奶牛和 $8$ 个牛栏（此时 $d=2$），可以将奶牛放置在位置 $1,3,5,8$ 或者 $1,3,6,8$，但不能放置在 $1,2,4,7$ 或者 $1,2,4,8$。 请帮助约翰尽可能有效地分散奶牛，并计算保证方案最优的情况下，所有奶牛需要移动的最小总距离。

- 第 $1$ 行：两个用空格分隔的整数：$N$ 和 $S$。 - 第 $2$ 到 $N+1$ 行：第 $i+1$ 行包含一个整数：$P_i$

- 第 $1$ 行：一个整数，奶牛们需要移动的最小总距离。保证答案小于 $10^9$ （因此可以使用 int 类型存储）。

**样例解释** 初始状态： | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:| |A|B|C|.|.|.|.|D|E|.| 奶牛从牛棚 2 移动到 3，从 3 移动到 5，从 9 移动到 10。总移动距离是 $1+2+1=4$。奶牛们的最终位置在牛棚 $1,3,5,8,10$。 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:| |移动前|A|B|C|.|.|.|.|D|E|.| |移动后|A|.|B|.|C|.|.|D|.|E| |移动距离|0|.|1|.|2|.|.|0|.|1|