项目排期 - 华为OD统一考试（C卷）

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

题目描述

项目组共有N个开发人员，项目经理接到了M个独立的需求，每个需求的工作量不同，且每个需求只能由一个开发人员独立完成，不能多人合作。

假定各个需求直接无任何先后依赖关系，请设计算法帮助项目经理进行工作安排，使整个项目能用最少的时间交付。

输入描述

第一行输入为M个需求的工作量，单位为天，用逗号隔开。 例如：X1 X2 X3 .... Xm 表示共有M个需求，每个需求的工作量分别为X1天，X2天......Xm天。其中0<M<30；0<Xm<200 第二行输入为项目组人员数量N 例如： 5 表示共有5名员工，其中0<N<10

输出描述

最快完成所有工作的天数 例如： 25 表示最短需要25天能完成所有工作

示例1

输入：
6 2 7 7 9 3 2 1 3 11 4
2

输出：
28

说明：
共有两位员工，其中一位分配需求6 2 7 7 3 2 1共需要28天完成，另一位分配需求9 3 11 4共需要27天完成，故完成所有工作至少需要28天。

题解

这道题可以使用二分查找 + 回溯来解决，二分的范围为需求工作量的最大值到总工作量的和。具体步骤如下：

1. 定义一个二分查找范围，最小值为需求工作量的最大值 - 1，最大值为总工作量的和。
2. 利用二分查找，查找最小的 MAX_SUM，使得每个人的工作量不超过 MAX_SUM。为了判断是否能满足条件，使用递归函数 ok （回溯法），在函数中模拟分配工作的过程，尝试将每个需求分配给不同的人员，看是否满足总工作量不超过 MAX_SUM。
3. 如果能满足条件，则缩小二分查找范围为左半部分；否则，缩小二分查找范围为右半部分。
4. 最终找到的二分查找范围左边界就是答案。

Java

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取每个工作的工作量
        int[] works = Arrays.stream(scanner.nextLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();

        // 读取开发人员的数量
        int N = scanner.nextInt();

        Solution solution = new Solution(works, N);
        System.out.println(solution.solve());
    }
}


class Solution {
    int N;
    int[] works;

    public Solution(int[] works, int N) {
        this.N = N;
        this.works = works;
    }

    public int solve() {
        // 二分查找，找到最小的 MAX_SUM，使得每个人的工作量 <= MAX_SUM
        int l = Arrays.stream(works).max().getAsInt() - 1;
        int r = Arrays.stream(works).sum();

        while (l + 1 < r) {
            int mid = (l + r) >> 1;
            if (ok(0, mid, new int[N])) {
                r = mid;
            } else {
                l = mid;
            }