H - National Day Parade
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Appoint description:
System Crawler (2014-11-08)
System Crawler (2014-11-08)
Description
There are n×n students preparing for the National Day parade on the playground. The playground can be considered as a n×m grid. The coordinate of the west north corner is (1,1) , and the coordinate of the east south corner is (n,m).
When training, every students must stand on a line intersection and all students must form a n×n square. The figure above shows a 3×8 playground with 9 students training on it. The thick black dots stand for the students. You can see that 9 students form a 3×3 square.
When training, every students must stand on a line intersection and all students must form a n×n square. The figure above shows a 3×8 playground with 9 students training on it. The thick black dots stand for the students. You can see that 9 students form a 3×3 square.
After training, the students will get a time to relax and move away as they like. To make it easy for their masters to control the training, the students are only allowed to move in the east-west direction. When the next training begins, the master would gather them to form a n×n square again, and the position of the square doesn’t matter. Of course, no student is allowed to stand outside the playground.
You are given the coordinates of each student when they are having a rest. Your task is to figure out the minimum sum of distance that all students should move to form a n×n square.
Input
There are at most 100 test cases.
For each test case:
The first line of one test case contain two integers n,m. (n<=56,m<=200)
Then there are n×n lines. Each line contains two integers, 1<=X i<=n,1<= Y i<=m indicating that the coordinate of the i th student is (X i , Y i ). It is possible for more than one student to stand at the same grid point.
For each test case:
The first line of one test case contain two integers n,m. (n<=56,m<=200)
Then there are n×n lines. Each line contains two integers, 1<=X i<=n,1<= Y i<=m indicating that the coordinate of the i th student is (X i , Y i ). It is possible for more than one student to stand at the same grid point.
The input is ended with 0 0.
Output
You should output one line for each test case. The line contains one integer indicating the minimum sum of distance that all students should move to form a n×n square.
Sample Input
2 168
2 101
1 127
1 105
2 90
0 0
2 101
1 127
1 105
2 90
0 0
Sample Output
41
题意:
有n*n学生本来站成n*n方阵((1,1)->(n,n)),现在左右移动了,告诉你之前的坐标和现在的坐标,求他们移动的最小距离
思路:
1. 此题只有左右移动,明显一行之内就只需要处理本行就行了
2. 数据范围不会超int
3. 原本的位置就是在最左边,现在相当于全是向右偏了,所以全部加起来-(1*n)*n/2即可
这是某io07的代码:
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
using namespace std;
int p[100][100];
int main()
{
int n,m,x,y;
while(scanf("%d %d",&n,&m)&&n&&m)
{
memset(p,0,sizeof(p));
for(int i=0;i<n*n;i++)
{
scanf("%d %d",&x,&y);
p[x][0]++;
p[x][p[x][0]]=y;
}
for(int i=1;i<=n;i++)
sort(p[i]+1,p[i]+n+1);
int sum=0,minn=1000000000;
for(int i=1;i<=m-n+1;i++)
{
sum=0;
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
{
sum+=abs(i-1+k-p[j][k]);
}
minn=min(sum,minn);
}
printf("%d\n",minn);
}
return 0;
}