http://acm./showproblem.php?pid=3687
在n*m排着n*n个士兵，休息时散开(只能水平散开)，集中时要重新站成n*n方阵，求总体最少移动步数
1.排序
2.枚举左边排开始站的列数，模拟计算每次站的花费
3.输出最小花费
#include <cstdio>#include <cstring>#include <cmath>#include <map>#include <set>#include <vector>#include <iostream>#include <algorithm>using namespace std;//const double eps=1e-7;//const double INF=1e50;//const double pi=acos(-1);#define N 60#define M 10000000int p[N][N],a[N];int main(){//freopen("a","r",stdin);int i,j,n,m,k;while (1){scanf("%d%d",&n,&m);if (n*m==0) break;int x,y;for (i=1;i<=n;i++) a[i]=0;for (i=1;i<=n*n;i++){scanf("%d%d",&x,&y);a[x]++;p[x][a[x]]=y;}for (i=1;i<=n;i++) sort(p[i]+1,p[i]+1+n);/*for (i=1;i<=n;i++){for (j=1;j<=n;j++) cout<<p[i][j]<<' ';cout<<"*******";}*/int Min=M;for (int yi=1;yi<=m-n+1;yi++){k=0;for (i=1;i<=n;i++){int yyi=yi;for (j=1;j<=n;j++){k+=abs(p[i][j]-yyi);yyi++;}}if (k<Min) Min=k;}printf("%d\n",Min);}return 0;}
