火车站选址---曼哈顿距离之和
"TLDR: 这个题目设计到曼哈顿距离，曼哈顿距离有一个性质，就是在中位数的位置，到其余所有为止的曼哈顿距离之和最小。但是这个题目并不需要用到这个性质，而是转化为前缀和的方法。"
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));
}
}