士兵排队问题 分治法

来自PTA的一道习题：

在一个划分成网格的操场上，n个士兵散乱地站在网格点上。网格点用整数坐标(x,y)表示。士兵们可以沿网格边往上、下、左、右移动一步，但在同一时刻任一网格点上只能有一名士兵。按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成(x,y),(x+1,y),…,(x+n-1,y)。如何选择x和y的值才能使士兵们以最少的总移动步数排成一行。

编程计算使所有士兵排成一行需要的最少移动步数。

输入格式:
第1行是士兵数n，1≤n≤10000。接下来n行是士兵的初始位置，每行有2个整数x和y，-10000≤x，y≤10000。

输出格式:
一个数据，即士兵排成一行需要的最少移动步数。

思路：

X轴和Y轴可以分开考虑。

士兵y轴坐标不变，可以假想为有一条垂直于y轴的直线，所有士兵都要移动到这条直线上，显然这是一个求中位数Y的问题。解决方法为将士兵y轴坐标排序，求得中位数后求各士兵y轴坐标据其的距离abs(y[i] - Y)
（排序不需要写了吧，我这里用的是快排

至此，在我们的假设中所有士兵已经移动到了同一水平线上，那么x轴的呢……有了y轴的思路，x轴应该也比较容易想到，它仍是一个求中位数的问题。
我们先对士兵x轴坐标进行排序，假设排序完他们坐标x0，x1，x2……x(n - 1)，而最终坐标为x，x+1，x+2……x+(n - 1)，那么移动步数也就是(x0 - x) + (x1 - x -1) + …… + (x(n - 1) - x - n）= (x0 - x) + ((x1 - 1) - x) + ((x2 - 2) - x) + …… + ((x(n - 1) - (n - 1) - x) 现在它已经转化为了求 x0，x1 - 1，x2 - 2……x(n - 1) - (n - 1)的中位数了

OK！上代码！

#include <stdio.h>
#include <math.h>

int x[10000], y[10000], s[10000];
    
void quickSort(int l, int r, int *data) 
{
    if(l >= r) return;
    int m = data[(l + r) / 2];//中间的那个
    int i = l;
    int j = r;
    while(i <= j)
    {
        while(data[i] < m)
            i++;
        while(data[j] > m)
            j--;
        if(i <= j)
        {//交换
            int tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
            i++;
            j--;
        }
    }//循环结束表示一趟已执行完
    if(l < j)
        quickSort(l, j, data);
    if(r > i)
        quickSort(i, r, data);
}

int main()
{
    int n, X, Y;
    int res = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &x[i]);
        scanf("%d", &y[i]);
    }
    
    //Y轴方向上的考虑 
    quickSort(0, n - 1, y);
    
    if(n % 2)
        Y = y[(n - 1) / 2];
    else Y = (y[n / 2] + y[n / 2 - 1]) / 2;
    
    for(int i = 0; i < n; i++)
    {
        res += abs(y[i] - Y);
    }
    
    //X轴方向上的考虑
    quickSort(0, n - 1, x);
    
    for (int i = 0; i < n; i++)
    {
        s[i] = x[i] - i;
    }
    
    quickSort(0, n - 1, s);
    
    if(n % 2)
        X = s[(n - 1) / 2];
    else X = (s[n / 2] + s[n / 2 - 1]) / 2;
    
    for(int i = 0; i < n; i++)
    {
        res += abs(s[i] - X);
    }
    
    printf("%d", res);
    
    return 0;
}

士兵排队问题 分治法

原文：https://www.cnblogs.com/chengjqyu/p/12504466.html