全网最全面的华为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; } }