算法题来源华为od机试A卷2022Q4

题目背景：给出找出服务中心该建立的位置到各个区域距离最小值

公司统计了该街道中所有区域在地图上的位置，并希望能够以此为依据为新的服务中心选址：使服务中心到所有区域的距离的总和最小。

给你一个数组 positions，其中 positions []=[left,right ]表示第1个区域在街道上的位置，其中 left 代表区域的左侧的起点， right 表示区域的右侧终点，

设择服务中心的位置为 location,如果第1个区城的右侧起点 right 满足 right < location ，

则第1个区域到服务中心的距离为 location – right ;

如果第 i 个区域的左侧起点 left 满足 left > location ，则第 i 个区城到服务中心的距离为 left – location ;

如果第 i 个区域的两侧 left , right 满足 left <= location <= right ，

则第1个区域到 服务中心的距离为0; 选择最佳的服务中心的位置为 location ，请返回最佳的服务中心位置到所有区域的距离总和的最小值。

输入描述

第一行，一个整数N表示区域个数。

后面N行，每行两个整数，表示区域的左右起点终点。

输出描述

运行结果输出一个整数，表示服务中心位置到所有区域的距离总和的最小值。

类似力扣这道题，但是是一维的

个人解法

然后是我个人的解法，最终只过了3成的用例

用二分法，左区间-1e9到右区间1e9

在我脑海中某点到各个区域的距离总和应该是一个V字型

我想象是这样的，所以我二分的判断就是n + 1到各点的距离是否比n大，是否是上升趋势，如果大的话就在左边区间

最后只通过了27.27%，以下是我的代码，后面我仔细想想，我觉得可能没我想的这么简单，看看各路大神有没有啥思路

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] areas = new int[n][2];
        for (int i = 0; i < n; i++) {
            areas[i][0] = sc.nextInt();
            areas[i][1] = sc.nextInt();
        }
//        Arrays.sort(areas, Comparator.comparingInt(o -> o[0]));
        int min1 = Integer.MAX_VALUE, max1 = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            min1 = Math.min(min1, areas[i][0]);
            max1 = Math.max(max1, areas[i][1]);
        }
        int l = min1, r = max1;
        long res = Long.MAX_VALUE;
        while (l < r) {
            int mid = (l + r) >> 1;
            long[] distances = getDistance(areas, mid);
            long d0 = distances[0], d1 = distances[1];
            if (d0 == d1) {
                System.out.println(d0);
                return;
            }
            if (d0 < d1) {
                r = mid;
            } else {
                l = mid + 1;
            }
            res = Math.min(d0, d1);
        }
        System.out.println(res);

    }
    // 返回x点到各个区域距离与x+1点到各个区域距离
    private static long[] getDistance(int[][] areas, int x) {
        long[] distances = new long[2];
        for (int[] area : areas) {
            int left = area[0], right = area[1];
            if (x < left) {
                distances[0] += (left - x);
            } else if (x > right) {
                distances[0] += (x - right);
            }

            if (x + 1 < left) {
                distances[1] += (left - (x + 1));
            } else if (x + 1 > right) {
                distances[1] += (x + 1 - right);
            }
        }
        return distances;
    }
}