记录编号	38326	评测结果	AAAAAAAAAA
题目名称	[USACO Open09] 放牧2	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	0.016 s
提交时间	2012-04-17 14:19:26	内存使用	11.71 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>

using namespace std;

const int oo=~0u>>2;

int N,S,ans,X[1000010],D,M,f[2][1000010];

int dp()
{
	for(int i=0;i<2;i++)
		for(int j=0;j<=M+1;j++)
			f[i][j]=oo;
	f[1][0]=abs(1-X[1]);
	f[0][0]=abs(1-X[1])+abs(X[2]-(1+D));
	f[0][1]=abs(1-X[1])+abs(X[2]-(2+D));
	for(int i=3;i<=N;i++)
	{
		f[i%2][0]=f[(i-1)%2][0]+abs(X[i]-(1+(i-1)*D));
		for(int j=1;j<=M&&j<i;j++)
			f[i%2][j]=min(f[(i-1)%2][j-1]+abs(X[i]-(1+(i-1-j)*D+(j-1)*(D+1)+D+1)),f[(i-1)%2][j]+abs(X[i]-(1+(i-2-j)*D+j*(D+1)+D)));
	}
	return f[N%2][M];
}

int main()
{
	freopen("graze2.in","r",stdin);
	freopen("graze2.out","w",stdout);
	scanf("%d%d",&N,&S);
	for(int i=1;i<=N;i++)
		scanf("%d",&X[i]);
	sort(X+1,X+1+N);
	D=(S-1)/(N-1);
	M=(S-1)%(N-1);
	printf("%d\n",dp());
	return 0;
}