火车站选址---曼哈顿距离之和

A 市计划新建一个火车站方便市民出行。

这里的道路十分规整，市民从位置(x1, y1)到位置(x2, y2)的路程为 |x1 - x2| + |y1 - y2| 。

经过前期考察，初步选定了M个可以建造火车站的位置。

为了尽可能节省市民到达火车站的时间，市长希望新建的车站离每位市民的总路程尽可能小。

请帮市长选出最合适新建火车站的位置。

输入格式

第一行有两个整数 N, M；分别表示市民的人数和可以建设火车站的位置

后面N行，每行 2 个整数 x_i, y_i，表示第i位市民的居住位置在 (x_i, y_i)

后面M行，每行 2 个整数p_i, q_i，表示第i个火车站候选位置在 (p_i, q_i)

输出格式

两个整数 p_i, q_i 表示最合适新建火车站的位置，若有多个答案，输出原始数据中第一个出现的

输入样例：

4 3

-1 -1

-1 1

1 -1

1 1

3 2

1 0

0 0

输出样例：

1 0

数据范围

1 <= N <= 100000

1 <= M <= 100000

-10000000 <= x_i, y_i, p_i, q_i <= 10000000

题解：

这个题目设计到曼哈顿距离，曼哈顿距离有一个性质，就是在中位数的位置，到其余所有为止的曼哈顿距离之和最小，但是这个题目并不需要用到这个性质，而是转化为前缀和，算是第一次遇到了。

先看看曼哈顿距离的中位数性质: 

|x - x1| + |x - y1| +  |x - x2| + |x - y2| + ... + |x - xn| + |x - yn|

= (|x - x1| + |x - x2| + ... + |x - xn|) + (|y - y1| + |y - y2| + ... + |y - yn|)

这个时候分别优化|x - x1| + |x - x2| + ... + |x - xn|的最小值和|y - y1| + |y - y2| + ... + |y - yn|的最小值

在数轴上画出x1 ~ x2就能轻易发现，在中位数的位置，x到各个x1~n的距离之和最小



但是这个题目指定了火车站的候选位置，因此改成前缀和的方法：

一个火车站到各个居民的曼哈顿距离之和可以用前缀和优化到O(1)时间复杂度



import java.util.Arrays;





public class Main {

    public static int[] solution(int n, int m, int[][] citizens, int[][] locations) {

        // Please write your code here

        // 这个题目用到了曼哈顿距离的性质，曼哈顿距离的最小值位于中位数的地方

        int [] xPos = new int[citizens.length];

        int [] yPos = new int[citizens.length];



        for(int i = 0; i < citizens.length; i ++ ) {

            xPos[i] = citizens[i][0];

            yPos[i] = citizens[i][1];

        }



        Arrays.sort(xPos);

        Arrays.sort(yPos);



        int[] prefixSumX = new int[citizens.length + 1];

        int[] prefixSumY = new int[citizens.length + 1];



        for(int i = 0; i < citizens.length; i ++) {

            prefixSumX[i + 1] = prefixSumX[i] + xPos[i];

            prefixSumY[i + 1] = prefixSumY[i] + yPos[i];

        }



        int [] res = new int[2];

        long distanceMin = Integer.MAX_VALUE;



        for(int i = 0; i < locations.length; i ++) {

            int idxOfX = Arrays.binarySearch(xPos, locations[i][0]);

            int idxOfY = Arrays.binarySearch(yPos, locations[i][1]);



            if(idxOfX < 0) idxOfX = - idxOfX - 1;

            if(idxOfY < 0) idxOfY = - idxOfY - 1;

            

            long distanceX = (long) locations[i][0] * idxOfX - prefixSumX[idxOfX] + 

                            (prefixSumX[n ] - prefixSumX[idxOfX]) - (long) locations[i][0] * (n - idxOfX);

            long distanceY = (long) locations[i][1] * idxOfY - prefixSumY[idxOfY] + 

                            (prefixSumY[n ] - prefixSumY[idxOfY]) - (long) locations[i][1] * (n - idxOfY);



            if(distanceX + distanceY < distanceMin) {

                distanceMin = distanceX + distanceY;

                res[0] = locations[i][0];

                res[1] = locations[i][1];

            }

        }



        return res;

    }



    public static boolean arrayEqual(int[] a, int[] b) {

        if (a.length!= b.length) {

            return false;

        }

        for (int i = 0; i < a.length; i++) {

            if (a[i]!= b[i]) {

                return false;

            }

        }

        return true;

    }



    public static void main(String[] args) {

        // You can add more test cases here

        int[][] citizens1 = {{11,23}, {0,15}, {19,13}, {6,14}, {24,6}, {16,21}, {15,20}, {22,0}, {0,4}, {3,20}, {1,14}, {20,18}, {25,5}, {2,0}, {0,14}, {5,22}, {14,18}, {18,16}, {21,24}, {25,14}, {14,18}, {20,9}, {17,4}, {11,24}, {16,20}};

        int[][] locations1 = {{25,10}, {4,17}, {20,17}, {9,24}, {17,22}, {3,3}, {11,16}, {22,22}, {22,17}, {20,16}, {22,21}, {1,11}, {8,21}, {8,6}, {13,18}};



        int[] result = solution(25, 15, citizens1, locations1);

        int[] expected = {13, 18};

        System.out.println(arrayEqual(result, expected));

    }

}