[Usaco2009 Open]Grazing2 移动牛棚
时间限制：3s 空间限制：128MB
题目描述
约翰有N(2≤N≤1500)头奶牛，S(N≤S≤1,000,000)个一字排开的牛棚．相邻牛棚间的距离恰好为1．
奶牛们已经回棚休息，第i只奶牛现在待在牛棚Pi．如果两只奶牛离得太近，会让奶牛们变得很暴躁．所以约翰想给一些奶牛换一个棚，让她们之间的距离变得尽量大，并且尽管接近．令d=Trunc((s-1)/(n-1))
所以约翰希望最终的奶牛的状态是：两只相邻奶牛间的距离与d之差不超过1，而且让尽量多的间距等于d．因此，对于4只奶牛8个棚的情况，1，3，5，8或1，3，6，8这样的安置情况是允许的，而1，2，4，7或1，2，4，8这样的情况是不允许的． 帮助约翰移动奶牛，让所有奶牛的移动距离之和最小，同时让最终的安置情况符合约翰心意．
输入格式
第1行输入N和S，接下来N行一行输入一个Pi．
输出格式
一个整数，表示最小的移动距离和．
样例输入
5 10 2 8 1 3 9
样例输出
4
提示
最终移成1，3，5，8，10.
题目来源
Silver