距离多点距离最近的点 中位数 boj1424-jiangwen127-ChinaUnix博客
http://blog.chinaunix.net/uid-20761674-id-74953.html
dalong 有一个n * n的棋盘，棋盘上有m个机器人。机器人分布在棋盘中不同的格子上，当然，有可能多个机器人在同一个棋盘上，每一次dalong可以对任意一个机器人操作， 使机器人向相邻的方向走一步（上下左右四个方向），当然，不能使机器人走出棋盘外。现在Dalong需要把所有的机器人移动到同一个位置（在哪个位置无所 谓，棋盘中任意一个格子都可），由于移动机器人需要耗费dalong一定的精力，因此他希望移动的总次数越少越好，你能帮助他吗？
下图是一个5*5的棋盘，有三个机器人，分别在（1，1）， （1 ， 2） ， （1 ， 4）
如果要把这三个机器人移到（1，2）这个格子中，一共需要3步：
1号机器人移动到（1，2）花费1步
2号机器人不移动
3号机器人移动到（1，2）花费2步
这是最少的移动步数
Input输入的第一行是一个正整数m(m <= 50)，表示棋盘中机器人的个数。
后面m行，每行2个数x，y，第i+1行表示第i个机器人在棋盘的位置，其中棋盘标号横向从左到右依次是1，2，…….n,纵向从上到下依次是 1，2，…..n，机器人坐标x,y的范围(1 <= x,y <= n)，其中1 <= n <= 1000000;
Output只有一行，最小的移动次数。保证答案小于2^31.
Sample Input
3
1 1
1 2
1 4
Sample Output
3
Hint输入样例2
4
15 16
16 15
14 15
15 14
输出样例 2
4
输入样例3
2
4 7
4 7
输出样例 3
0
1424
此题主要用到了分治的思想,还有一个简单的定理:
到线段AB的距离和最小的点必然在线段AB之间
所以可以分别求到所有横坐标距离之和最小的x值,
和到所有纵坐标距离和最小的y值,
然后计算出结果
求x和y就用到了这个定理
先把所有x从小到大排序,
x[0],x[1],x[2],...x[n-1]
取位于线段x[0]x[n-1],x[1]x[n-2],x[2]x[n-3].....
之间的x值即为所求
这里可以取下标为中位数那个x[i]即为所求的x
y的求法同理
什么是中位数：
将数据排序后，位置在最中间的数值。即将数据分成两部分，一部分大于该数值，一部分小于该数值。中位数的位置：当样本数为奇数时，中位数=(N+1)/2 ; 当样本数为偶数时，中位数为N/2与1+N/2的均值
int xx[60], yy[60];
int cmp(const void *a, const void *b)
{
int *pa = (int *)a;
int *pb = (int *)b;
return *pa - *pb;
}
unsigned int find_steps(int x_mid, int y_mid, int size)
{
unsigned int i, sum;
sum = 0;
for (i=0 ; i {
sum += (abs(xx[i] - x_mid) + abs(yy[i] - y_mid));
}
return sum;
}
int main(int argc, char *argv[])
{
int m, i, x, y, x_mid, y_mid;
unsigned steps;
scanf("%d", &m);
for (i=0 ; i {
scanf("%d %d", &xx[i], &yy[i]);
}
qsort(xx, m, sizeof(int), cmp);
qsort(yy, m, sizeof(int), cmp);
/*求出x,y方向上的中位数*/
if (0 != m % 2)
{
x_mid = xx[m / 2];
y_mid = yy[m / 2];
}
else
{
x_mid = (xx[m/2 - 1] + xx[m / 2]) / 2;
y_mid = (yy[m/2 - 1] + yy[m / 2]) / 2;
}
/*求出所有点距离中位数的距离之和*/
steps = find_steps(x_mid, y_mid, m);
printf("%d\n", steps);
}
Related: Zenefits: Robert Merge Point
Read full article from 距离多点距离最近的点 中位数 boj1424-jiangwen127-ChinaUnix博客
http://blog.chinaunix.net/uid-20761674-id-74953.html
dalong 有一个n * n的棋盘，棋盘上有m个机器人。机器人分布在棋盘中不同的格子上，当然，有可能多个机器人在同一个棋盘上，每一次dalong可以对任意一个机器人操作， 使机器人向相邻的方向走一步（上下左右四个方向），当然，不能使机器人走出棋盘外。现在Dalong需要把所有的机器人移动到同一个位置（在哪个位置无所 谓，棋盘中任意一个格子都可），由于移动机器人需要耗费dalong一定的精力，因此他希望移动的总次数越少越好，你能帮助他吗？
下图是一个5*5的棋盘，有三个机器人，分别在（1，1）， （1 ， 2） ， （1 ， 4）
如果要把这三个机器人移到（1，2）这个格子中，一共需要3步：
1号机器人移动到（1，2）花费1步
2号机器人不移动
3号机器人移动到（1，2）花费2步
这是最少的移动步数
Input输入的第一行是一个正整数m(m <= 50)，表示棋盘中机器人的个数。
后面m行，每行2个数x，y，第i+1行表示第i个机器人在棋盘的位置，其中棋盘标号横向从左到右依次是1，2，…….n,纵向从上到下依次是 1，2，…..n，机器人坐标x,y的范围(1 <= x,y <= n)，其中1 <= n <= 1000000;
Output只有一行，最小的移动次数。保证答案小于2^31.
Sample Input
3
1 1
1 2
1 4
Sample Output
3
Hint输入样例2
4
15 16
16 15
14 15
15 14
输出样例 2
4
输入样例3
2
4 7
4 7
输出样例 3
0
1424
此题主要用到了分治的思想,还有一个简单的定理:
到线段AB的距离和最小的点必然在线段AB之间
所以可以分别求到所有横坐标距离之和最小的x值,
和到所有纵坐标距离和最小的y值,
然后计算出结果
求x和y就用到了这个定理
先把所有x从小到大排序,
x[0],x[1],x[2],...x[n-1]
取位于线段x[0]x[n-1],x[1]x[n-2],x[2]x[n-3].....
之间的x值即为所求
这里可以取下标为中位数那个x[i]即为所求的x
y的求法同理
什么是中位数：
将数据排序后，位置在最中间的数值。即将数据分成两部分，一部分大于该数值，一部分小于该数值。中位数的位置：当样本数为奇数时，中位数=(N+1)/2 ; 当样本数为偶数时，中位数为N/2与1+N/2的均值
int xx[60], yy[60];
int cmp(const void *a, const void *b)
{
int *pa = (int *)a;
int *pb = (int *)b;
return *pa - *pb;
}
unsigned int find_steps(int x_mid, int y_mid, int size)
{
unsigned int i, sum;
sum = 0;
for (i=0 ; i
sum += (abs(xx[i] - x_mid) + abs(yy[i] - y_mid));
}
return sum;
}
int main(int argc, char *argv[])
{
int m, i, x, y, x_mid, y_mid;
unsigned steps;
scanf("%d", &m);
for (i=0 ; i
scanf("%d %d", &xx[i], &yy[i]);
}
qsort(xx, m, sizeof(int), cmp);
qsort(yy, m, sizeof(int), cmp);
/*求出x,y方向上的中位数*/
if (0 != m % 2)
{
x_mid = xx[m / 2];
y_mid = yy[m / 2];
}
else
{
x_mid = (xx[m/2 - 1] + xx[m / 2]) / 2;
y_mid = (yy[m/2 - 1] + yy[m / 2]) / 2;
}
/*求出所有点距离中位数的距离之和*/
steps = find_steps(x_mid, y_mid, m);
printf("%d\n", steps);
}
Related: Zenefits: Robert Merge Point
Read full article from 距离多点距离最近的点 中位数 boj1424-jiangwen127-ChinaUnix博客
