Train station location---sum of distances from Manhattan
"TLDR: This question is designed to the Manhattan distance. The Manhattan distance has a property, that is, at the median position, the sum of the Manhattan distances to all the rest is the smallest. But this question does not require the use of this property, but the method of converting it into a prefix sum."
City A plans to build a new train station to facilitate citizens' travel.
The roads here are very regular. The distance traveled by citizens from location (x1, y1) to location (x2, y2) is |x1 - x2| + |y1 - y2|.
After preliminary inspection, M locations where railway stations can be built were initially selected.
In order to save as much time as possible for citizens to reach the train station, the mayor hopes that the total distance between the new station and each citizen will be as small as possible.
Please help the mayor choose the most suitable location for the new train station.
Input format
The first line has two integers N, M; respectively representing the number of citizens and the location where a train station can be built
The following N lines, each line contains 2 integers x_i, y_i, indicating that the residence location of the ith citizen is in (x_i, y_i)
The following M lines, each line contains 2 integers p_i, q_i, indicating that the ith train station candidate location is at (p_i, q_i)
Output format
Two integers p_i, q_i represent the most suitable location for the new railway station. If there are multiple answers, output the first one that appears in the original data.
Input sample:
4 3
-1 -1
-1 1
1 -1
1 1
3 2
1 0
0 0
Output sample:
1 0
Data range
1 <= N <= 100000
1 <= M <= 100000
-10000000 <= x_i, y_i, p_i, q_i <= 10000000
Solution:
This question is designed to the Manhattan distance. The Manhattan distance has a property, that is, at the position of the median, the sum of the Manhattan distances to all the rest is the smallest. However, this question does not need to use this property, but converts it into a prefix sum. This is the first time I have encountered it.
Let’s first look at the median properties of Manhattan distance:
|x - x1| + |x - y1| + |x - x2| + |x - y2| + ... + |x - xn| + |x - yn|
= (|x - x1| + |x - x2| + ... + |x - xn|) + (|y - y1| + |y - y2| + ... + |y - yn|)
At this time, optimize the minimum value of |x - x1| + |x - x2| + ... + |x - xn| and the minimum value of |y - y1| + |y - y2| + ... + |y - yn|
By drawing x1 ~ x2 on the number line, you can easily find that at the median position, the sum of the distances from x to each x1 ~ n is the smallest.
However, this question specifies the candidate location of the train station, so it is changed to the prefix sum method:
The sum of Manhattan distances from a train station to various residents can be optimized to O(1) time complexity using prefix sum
import java.util.Arrays;
public class Main {
public static int[] solution(int n, int m, int[][] citizens, int[][] locations) {
// Please write your code here
// This question uses the properties of Manhattan distance. The minimum value of Manhattan distance is located at the median.
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));
}
}