华为OD机试 - 部门人力分配 - 二分查找（Java 2024 D卷 200分）

在这里插入图片描述

华为OD机试 2024D卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（D卷+C卷+A卷+B卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

部门在进行需求开发时需要进行人力安排。当前部门需要完成 N 个需求，需求用 requirements[i] 表示，requirements[i] 表示第 i 个需求的工作量大小，单位：人月。这部分需求需要在 M 个月内完成开发，进行人力安排后每个月的人力是固定的。

目前要求每个月最多有 2 个需求开发，并且每个月需要完成的需求不能超过部门人力。请帮部门评估在满足需求开发进度的情况下，每个月需要的最小人力是多少？

二、输入描述

输入第一行为 M ，第二行为 requirements 。

M 表示需要开发时间要求，requirements 表示每个需求工作量大小

N 为 requirements 长度，1 ≤ N / 2 ≤ M ≤ N ≤ 10000，1 ≤ requirements[i]≤ 10^9

三、输出描述

对于每一组测试数据，输出部门需要人力需求，行末无多余的空格。

四、解题思路

本题要求我们在给定的开发时间（以月份为单位）内完成一系列需求开发，每个月最多完成2个需求，并且每个月需要的总人力（工作量）不能超过一个固定值。目标是找到每个月需要的最小人力。

为了实现这一目标，我们可以使用二分查找和贪心算法相结合的策略：

确定二分查找的范围：
- 最小值 minCapacity：为单个需求的最大工作量，因为至少需要满足最重的需求。
- 最大值 maxCapacity：为两个最重需求的工作量之和，这是最极端的情况下的最大人力需求。
二分查找：
- 通过二分查找的方法，在 minCapacity 和 maxCapacity 之间找到最小的每月人力需求。
- 每次取中间值 midCapacity，检查在这个人力值下是否可以在规定的 months 内完成所有需求。
- 如果可以，说明当前人力值可能是一个解，但需要尝试更小的值以找到最优解；如果不可以，说明当前人力值太小，需要增加人力值。
检查可行性：
- 使用贪心算法检查在给定的每月人力值下是否可以在规定的 months 内完成所有需求。
- 从工作量最小的需求和工作量最大的需求开始，尽量将两个需求安排在同一个月内。如果不能，就安排一个需求。
- 记录需要的月份数，并与规定的 months 进行比较。

五、Java算法源码

public class Test01 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取开发时间要求的月份数
        int months = Integer.parseInt(scanner.nextLine());

        // 读取每个需求的工作量，并转换为整数数组
        int[] workload = Arrays.stream(scanner.nextLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();

        // 输出计算得到的最小人力需求
        System.out.println(calculateMinManpower(months, workload));
    }

    /**
     * 计算满足开发进度的最小人力需求
     * @param months 需要开发的总月份数
     * @param workload 每个需求的工作量数组
     * @return 最小人力需求
     */
    public static long calculateMinManpower(int months, int[] workload) {
        Arrays.sort(workload); // 将需求工作量数组进行排序
        int numOfTasks = workload.length; // 获取需求的总数量

        // 如果只有一个需求，则返回该需求的工作量
        if (numOfTasks == 1) {
            return workload[0];
        }

        // 初始化二分查找的最小值和最大值
        long minCapacity = workload[numOfTasks - 1]; // 最小人力需求为最大工作量
        long maxCapacity = workload[numOfTasks - 2] + workload[numOfTasks - 1]; // 最大人力需求为最大的两个工作量之和
        long optimalCapacity = maxCapacity; // 初始最优人力需求设为最大值

        // 进行二分查找
        while (minCapacity <= maxCapacity) {
            long midCapacity = (minCapacity + maxCapacity) >> 1; // 计算中间值

            // 检查在当前中间值下是否能在规定月份内完成所有需求
            if (canCompleteWithinMonths(midCapacity, months, workload)) {
                optimalCapacity = midCapacity; // 更新最优人力需求
                maxCapacity = midCapacity - 1; // 尝试更小的值
            } else {
                minCapacity = midCapacity + 1; // 尝试更大的值
            }
        }

        return optimalCapacity; // 返回计算得到的最优人力需求
    }

    /**
     * 检查是否可以在给定的月份内完成所有需求
     * @param capacity 每个月的最大工作量
     * @param months 总月份数
     * @param workload 每个需求的工作量数组
     * @return 是否可以在给定的月份内完成所有需求
     */
    public static boolean canCompleteWithinMonths(long capacity, int months, int[] workload) {
        int left = 0; // 指向工作量最小的需求
        int right = workload.length - 1; // 指向工作量最大的需求
        int requiredMonths = 0; // 记录需要的月份数

        // 遍历需求，尝试将两个需求放在同一个月份内完成
        while (left <= right) {
            if (workload[left] + workload[right] <= capacity) {
                left++; // 如果最小需求和最大需求可以一起完成，则移动左指针
            }
            right--; // 总是移动右指针
            requiredMonths++; // 增加需要的月份数
        }

        return months >= requiredMonths; // 判断给定的月份是否足够
    }
}