题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=3687题目大意： 在n*m排着n*n个士兵，休息时散开(只能水平散开)，集中时要重新站成n*n方阵，求总体最少移动步数
题解：注意是只能水平散开，所以该题也成为水题了
1.排序
2.枚举左边排开始站的列数，模拟计算每次站的花费
3.输出最小花费
代码：
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
int n,m;
struct Point
{
int x;
int y;
friend bool operator < (const Point &_p1,const Point & _p2)
{
if(_p1.x == _p2.x)
return _p1.y < _p2.y;
else
return _p1.x < _p2.x;
}
};
Point points[3600];
void Test()
{
int size = n*n;
int x1,y1;
for(int i = 0; i < size; ++i)
{
scanf("%d %d",&x1,&y1);
points[i].x = x1;
points[i].y = y1;
}
sort(points,points+size);
int ans = 1 << 30;
//枚举列数
for(int i = 1; i <= m-n+1; ++i)
{
int ans2 = 0;
int k = 0;
//n*n布局
for(int x = 0; x < n; ++x)
{
for(int y = 0; y < n; ++y)
{
//水平相减
ans2 += abs(i+y - points[k].y);
++k;
}
}
ans = min(ans,ans2);
}
printf("%d\n",ans);
}
int main()
{
while(scanf("%d %d",&n,&m) != EOF)
{
if(n == 0 || m == 0)
break;
Test();
}
return 0;
}posted on 2010-11-11 13:45
bennycen 阅读(453)
评论(0) 编辑 收藏 引用 所属分类:
算法题解