题意概括
有\(n\)个奶牛,\(s\)个牛棚,要求每个奶牛只能距离为\(d\)或\(d+1\),\(d=(n-1)/(s-1)\),问奶牛的最小移动距离
先把奶牛的位置排个序经过思考可以发现第一头奶牛在牛棚\(1\),第\(n\)头奶牛在牛棚\(s\),奶牛间的距离只能是\(d\)或\(d+1\),且题目要求距离尽可能大那距离为\(d\)的数量和距离为\(d+1\)的数量就可以固定下来了.
\(f[i][j]\)表示前\(i\)头奶牛,有\(j\)头与上一头的距离为\(d+1\)的最小移动距离
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N=1600;
int n,s,m,d,p[N];
int f[N][N];
int main(){
// freopen("s.in","r",stdin);
scanf("%d%d",&n,&s);
d=(s-1)/(n-1);
m=s-d*(n-1);
for(int i=1;i<=n;++i)scanf("%d",&p[i]);
sort(p+1,p+n+1);
memset(f,0x3f,sizeof(f));
f[1][1]=p[1]-1;//第1头奶牛算作也是距离为d+1便于转移
for(int i=2;i<=n;++i){
//第i头奶牛在(i-1)*d+j的位置
for(int j=min(m,i);j>=1;--j){
f[i][j]=min(f[i-1][j],f[i-1][j-1])+abs(p[i]-(i-1)*d-j);
}
}
printf("%d",f[n][m]);
return 0;
}