原题：

Grazing2 S

时间限制: 1 Sec  内存限制: 125 MB

题目描述

Farmer John has N (2 <= N <= 1,500) prize milk cows conveniently numbered 1..N. His newly-painted barn has S (N <= S <= 1,000,000) stalls (conveniently numbered 1..S) in a single long line; each stall is a unit distance from its neighboring stall(s).

The cows have made their way to the stalls for a rest; cow i is in stall P_i. Antisocial as they are, the cows get grumpy if they are situated in stalls very close to each other, so Farmer John wants to move the cows to be as spread out as possible.

FJ wants to make sure that the N - 1 distances between adjacent cows are as large as possible, and he would also like them to be similar to each other (i.e., close to equi-distant spacing).

In particular, FJ would like all distances between adjacent cows to be at most 1 different from (S - 1) / (N - 1), where integer division is used. Moreover, he would like as many of these distances as possible to be exactly equal to (S - 1) / (N - 1) [integer

division]. Thus, with four cows and eight stalls, one can place the cows at positions 1, 3, 5, 8 or 1, 3, 6, 8 but not at 1, 2, 4, 7 or 1, 2, 4, 8.

Help FJ spread the cows as efficiently as possible by calculating and reporting the minimum total distance that the cows have to move in order to achieve proper spacing. Ignore the distance it takes for a cow to enter or exit a stall.

输入

* Line 1: Two space-separated integers: N and S

* Lines 2..N+1: Line i+1 contains the single integer: P_i

输出

* Line 1: A single integer: the minimum total distance the cows have to travel. This number is guaranteed to be under 1,000,000,000 (thus fitting easily into a signed 32-bit integer).

样例输入

5 10 
2 
8 
1 
3 
9 

样例输出

4 

提示

1 2 3 4 5 6 7 8 9 10

Cow Locs | A | B | C | . | . | . | . | D | E | . |

Cows move from stall 2 to 3, 3 to 5, and 9 to 10. The total distance moved is 1 + 2 + 1 = 4. The final positions of the cows are in stalls 1, 3, 5, 8, and 10.

1 2 3 4 5 6 7 8 9 10

Init Stall | A | B | C | . | . | . | . | D | E | . | Final Stall | A | . | B | . | C | . | . | D | . | E | Distance moved | 0 | . | 1 | . | 2 | . | . | 0 | . | 1 |

 

---

 

 

[原题链接]

 

题目大意：

　　每头奶牛有一个初始位置Pi，将奶牛们重新排列，使得每两头奶牛距离与d=Trunc((s-1)/(n-1))只差不大于1。

---

 

 

解题思路：

　　首先，d是一个确定的值。那么每两头奶牛的距离只能是n-1，n，n+1中的一个。

　　既然要让尽可能多的奶牛间距为n，那么可以用一个n-1和一个n+1换成两个n。根据d的定义可以知道d-1的数量一定小于n+1的数量。

　　因此，所有奶牛之间距离只能是n或者是n+1。

　　因为要让所有奶牛之间距离尽可能大，所以1号牛棚与n号牛棚一定都有奶牛。换句话说，这若干个d和若干个d+1的和总为给定的值m-1。

　　那么n-1的数量就是m-1-d*(n-1)，其余的就是n的数量（这个应该小学就会推了，不解释）

　　现在，我们已经知道了所有奶牛之间的间距的所有情况。很容易想到DP的思路。

　　令f[i][j]表示前i个间距中有j个是n+1，i-j个是n，f[i][j]=min(f[i-1][j],f[i-1][j-1])+当前点到现在的位置的距离。

　　转移方程的意思很好理解，即要么当前的间距是n（相当于j的数量不变），要么当前间距是n+1（相当于j的数量加了一）

　　初始定义：第一头奶牛一定在第一位，移动其他奶牛需要更多代价，f[1][1]=a[1]-1。

　　p.s.不要忘记排序，否则样例都过不了

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<string.h>
 4 using namespace std;
 5 const int N=2e3+5;
 6 int a[N],f[N][N],n,m,d;
 7 int main()
 8 {
 9     memset(f,63,sizeof f);
10     scanf("%d%d",&n,&m);
11     for(int i=1;i<=n;i++)  scanf("%d",&a[i]);
12     sort(a+1,a+n+1);
13     d=(m-1)/(n-1),f[1][0]=a[1]-1;
14     for(int i=2;i<=n;i++)
15         for(int j=0;j<=min(i-1,m-1-d*(n-1));j++)
16             f[i][j]=min(f[i-1][j],f[i-1][j-1])+abs(a[i]-1-((i-1)*d+j));
17     printf("%d",f[n][m-1-d*(n-1)]);
18 return 0;