距离多点距离最近的点 中位数 boj1424

962阅读 0评论2010-01-07 jiangwen127
分类:

Robot
Submit: 218   Accepted:85
Time Limit: 2000MS  Memory Limit: 65536K
Description
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的均值  


#include 
#include 

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);
}
 
上一篇:SPFA
下一篇:怎样写简历及其它