LOADING

百度&必应权4, 日IP1w+ 查看详情
自助收录

2023年华为OD机考真题:服务中心的最佳位置

算法刷题2年前 (2023)更新 江南白衣
844 0 0
2023年华为OD机考真题:服务中心的最佳位置

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

 

© 版权声明

相关文章

暂无评论

暂无评论...