题目描述
一个快递公司希望在一条街道建立新的服务中心。公司统计了该街道中所有区域在地图上的位置，并希望能够以此为依据为新的服务中心选址: 使服务中心到所有区域的距离的总和最小。
给你一个数组positions，其中positions = [left, right] 表示第i个区域在街道上的位置
其中left代表区域的左侧的起点，right代表区域的右侧终点，假设服务中心的位置为location
- 如果第
i个区域的右侧终点right满足right< location，则第i个区域到服务中心的距离为location - right - 如果第
i个区域的左侧起点left满足left >location，则第i个区域到服务中心的距离为left-location - 如果第
i个区域的两侧left, right满足left <= location <= right，则第i个区域到服务中心的距离为0
选择最佳的服务中心位置为location，请返回最佳的服务中心位置到所有区域的距离总和的最小值
输入描述
先输入区域数组 positions 的长度n
- 接下来
行，每行输入成对的
和
值，以空格隔开
输出描述
输出为 的值
用例
用例一
--输入
3
1 2
3 4
10 20
--输出
8
--说明
无
用例二
--输入
2
1 4
4 5
--输出
0
--说明
无
用例三
--输入
4
5 6
1 8
7 15
2 4
--输出
3
--说明
无
用例四
--输入
6
1 3
4 9
2 15
6 27
15 17
5 8
--输出
12
用例五
--输入
16
41 67
0 34
24 69
58 78
62 64
5 45
27 81
61 91
42 95
27 36
4 91
2 53
82 92
16 21
18 95
26 47
--输出
127题目解析
- 根据题目可以得到，所有的区域都在一条坐标线上。
- 那么可以对 区域数组
positions进行排序，记录数组长度为n - 很显然
location的位置选择应该在{positions[0][0], positions[n-1][1]}之间
- 这一点不论证，画画图很轻松看出来。
- 然后这里直观地可以用二分法来解决，因为最佳位置肯定是在
{positions[0][0], positions[n-1][1]}之间 - 但是这个时候产生问题了，没有办法选取一个 “参考值” 来执行二分法
- 回到题目中的问题，假设有一点作为最佳服务中心位置满足 ：“到所有区域的距离总和的值最小”
- 那么该点，向左或者向右移动的话，距离总和是增大的。如下图
- 如何求这个极值呢？
- 这里需要运用到“三分法” 的知识
三分法
结合题目理解
- 由之前分析，可以得到
positions数组，最左边和最右边的位置坐标，分别记为min,max由此可以得到中心点mid - 如下图
- 根据图示，服务中心的最佳选址位置在 点
mid - 那么现在问题变成了，如何求得
mid点所在的位置.
- 如下图，考虑一种最简单的情况。
- 点 1，3 对应计算出来的距离总和为 b ，点 2 计算出来的距离总和为 a
- 很显然
- 最佳选址位置应该选在点 2
- 那么想要找到 最佳选址位置，在计算过程中需要确定 3 个点
- 一个是中心点 计算出的距离总和记为
mid_distance - 一个是中心点左边的点 计算出的距离总和记为
left_distance - 一个是中心点右边的点 计算出的距离总和记为
right_distance - 三个点计算出来的距离，有以下几种情况
- 根据选点示例，每一次选择三个点，然后分别计算距离总和。
- 如果出现 case1 图示情况，证明选点需要向右移，因为很显然，“极值”在右边，三个点一起移动
- 如果出现 case2 图示情况，证明选点需要向左移，因为很显然，“极值”在左边，三个点一起移动
- 直到找到 -- “最佳选址”
show code
import java.util.Scanner;
/**
* desc : <a href="https://blog.csdn.net/qfc_128220/article/details/128808359">服务中心选址</a>
* <p>
* create time : 2023/9/5 17:20
*/
public class ServiceCenterSiteSelection {
public static void main(String[] args) {
double l = 1e-5;
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int n = in.nextInt();
int[][] positions = new int[n][2];
for (int i = 0; i < n; i++) {
positions[i][0] = in.nextInt();
positions[i][1] = in.nextInt();
}
serviceCenterSiteSelection(positions);
}
}
private static void serviceCenterSiteSelection(int[][] positions) {
// 首先去拿到 最左边 和 最右边的坐标
double min_left = Integer.MAX_VALUE,max_right = 0;
for (int[] position : positions) {
min_left = Math.min(position[0], min_left);
max_right = Math.max(position[1], max_right);
}
// 1e-5：表示 10 的 -5 次方，即 0.00001.
double eps = 1e-5;
while(max_right - min_left >= eps) {
// 进行三等分
double k = (max_right - min_left) / 3;
double m_l = min_left + k;
double m_r = max_right - k;
// 计算 mid 偏左边的位置.
double l_distance = dealDistance(positions, m_l);
// 计算 mid 偏右边的位置.
double r_distance = dealDistance(positions, m_r);
if(l_distance < r_distance) {
max_right = m_r;
} else {
min_left = m_l;
}
}
// 此时 点 min_left ：为最佳估计点，最接近 最佳选址位置.
System.out.println((int) dealDistance(positions, min_left));
}
private static double dealDistance(int[][] positions, double mid) {
double ans = 0;
for (int[] position : positions) {
double l = position[0], r = position[1];
if(l > mid) {
// 在左边
ans += l - mid;
} else if(r < mid) {
ans += mid - r;
}
}
return ans;
}
}