全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。
真题库：https://www.yuque.com/codernav.com/od
题目：服务中心的最佳位置
知识点：二分查找、双指针
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
一家快递公司希望在一条街道建立新的服务中心。公司统计了该街道中所有区域在地图上的位置，并希望能够以此为依据为新的服务中心选址：使服务中心 到所有区域的距离的总和最小。
给你一个数组 positions ，其中 positions[i] = [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（1 <= n <= 10^5）
接下来n行每行输入成对的left和right值，以空格隔开
-10^9 <left <= 10^9
-10^9 <right<= 10^9
输出描述：
输出为location
补充说明：
不同的 positions 的区间可能存在重叠；
location 的位置可以有多个
示例1
输入：
3
1 2
3 4
10 20
输出：
8
说明：
我们选择最佳服务中心位置为3，此时3到 区域[1,2]的距离为1, 3到区域[3,4]的距离为0,3到区域[10,20]的距离为7。最小的距离为8。
示例2
输入：
2
1 4
4 5
输出：
0
说明：
我们选择最佳服务中心位置可以选择4,此时的最小距离为0
示例3
输入：
4
1 3
2 6
8 10
15 18
输出：
14
说明：
我们选择最佳服务中心位置可以选择7,此时的最小距离为14
解题思路：
算法一：
暴力计算所有位置到各街道距离和，求出其中最小值；
算法二：使用二分法
计算最左侧到各街道的距离和left，最右侧到各街道的距离和right，中间位置到各街道的距离和mid；
如果left<right，则right=mid；否则left=mid；以此类推。。。
这道题的正确率也是感人，我看到的最高分是54分。以下是找到的真机用例：
4 4 5 6 1 8 7 15 2 4 正确答案：3
2 2 1 4 4 5 正确答案：0
5 6 1 3 4 9 2 15 6 27 15 17 5 8 正确答案：12
10 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
算法一代码实现：
package com.codernav.demo.hwod.exam;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* @title 服务中心的最佳位置
* @Description 一家快递公司希望在一条街道建立新的服务中心。公司统计了该街道中所有区域在地图上的位置，并希望能够以此为依据为新的服务中心选址：使服务中心 到所有区域的距离的总和最小。
* 给你一个数组 positions ，其中 positions[i] = [left, right] 表示第 i 个区域在街道上的位置，其中 left 代表区域的左侧的起点， right 表示区域的右侧终点，设择服务中心的位置为 location。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/28
*/
public class Main {
public static List<int[]> list = new ArrayList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
int[] ints = new int[2];
ints[0] = sc.nextInt();
ints[1] = sc.nextInt();
list.add(ints);
}
/**
* 对线段进行排序
* 左边界小的在前
* 左边界相等的右边界小的在前
*/
list.sort((a, b) -> {
if (a[0] == b[0]) {
return a[1] - b[1];
}
return a[0] - b[0];
});
//最左边的坐标
int min = list.get(0)[0];
//最右边的坐标
int max = list.get(n - 1)[1];
//距离最小值
int res = Integer.MAX_VALUE;
for (int i = min; i <= max; i++) {
res = Math.min(res, handle(i));
}
System.out.println(res);
}
/**
* 求出服务中心到所有街道的距离和
*
* @param mid
* @return
*/
public static int handle(int mid) {
int res = 0;
for (int[] ints : list) {
int a = ints[0];
int b = ints[1];
if (mid < a) {
res += a - mid;
} else if (mid > b) {
res += mid - b;
}
}
return res;
}
}
算法二代码实现：
package com.codernav.demo.hwod.exam;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* @title 服务中心的最佳位置
* @Description 一家快递公司希望在一条街道建立新的服务中心。公司统计了该街道中所有区域在地图上的位置，并希望能够以此为依据为新的服务中心选址：使服务中心 到所有区域的距离的总和最小。
* 给你一个数组 positions ，其中 positions[i] = [left, right] 表示第 i 个区域在街道上的位置，其中 left 代表区域的左侧的起点， right 表示区域的右侧终点，设择服务中心的位置为 location。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/28
*/
public class Main {
public static List<int[]> list = new ArrayList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
int[] ints = new int[2];
ints[0] = sc.nextInt();
ints[1] = sc.nextInt();
list.add(ints);
}
/**
* 对线段进行排序
* 左边界小的在前
* 左边界相等的右边界小的在前
*/
list.sort((a, b) -> {
if (a[0] == b[0]) {
return a[1] - b[1];
}
return a[0] - b[0];
});
int left = list.get(0)[0];
int right = list.get(n - 1)[1];
//最左侧到各街道的距离和
int leftDance = handle(left);
//最右侧到各街道的距离和
int rightDance = handle(right);
while (right - left > 1) {
//中心位置
int mid = (right + left) / 2;
//中心位置到各街道的距离总和
int midDance = handle(mid);
//距离和较小的位置
int min = Math.min(leftDance, rightDance);
if (leftDance == min) {
//左侧位置较小则右侧变成中心位置
right = mid;
rightDance = midDance;
} else {
//右侧位置较小则左侧变成中心位置
left = mid;
leftDance = midDance;
}
}
System.out.println(Math.min(leftDance, rightDance));
}
/**
* 求出所有距离和
*
* @param mid
* @return
*/
public static int handle(int mid) {
int res = 0;
for (int[] ints : list) {
int a = ints[0];
int b = ints[1];
if (mid < a) {
res += a - mid;
} else if (mid > b) {
res += mid - b;
}
}
return res;
}
}
相关文章
