项目排期 - 华为OD统一考试

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

alt

题目描述

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

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;
            }
        }

        return r;
    }

    // 递归判断工作能否分配给 N 个人，使得每个人的总工作量 <= MAX_SUM
    private boolean ok(int idx, final int MAX_SUM, int[] sums) {
        if (idx == works.length) {
            return true;
        }

        for (int i = 0; i < N; i++) {
            // 尝试将 idx 个工作分配给第 i 个人员
            if (sums[i] + works[idx] <= MAX_SUM) {
                sums[i] += works[idx];
                if (ok(idx + 1, MAX_SUM, sums)) { // 可以完成分配，则直接返回 true
                    return true;
                }
                sums[i] -= works[idx];
            }
        }

        return false;
    }
}

Python

from typing import List


works = list(map(int, input().split()))
N = int(input())


def ok(idx: int, MAX_SUM: int, sums: List[int]) -> bool:
    """
    :param idx: 索引下标
    :param MAX_SUM: 每人总工作量的限制（最大值）
    :param sums:  sums[i] 表示第 i 个人需求的总工作量
    :return: 工作能否分配给 N 个人，使得每个人的总工作量 <= MAX_SUM
    """

    global N
    if idx == len(works):
        return True

    for i in range(N):
        if sums[i] + works[idx] <= MAX_SUM:  # 尝试将 idx 个工作分配给第 i 个人员
            sums[i] += works[idx]
            if ok(idx + 1, MAX_SUM, sums):
                return True
            sums[i] -= works[idx]

    return False


# 二分查找，找到最小的 MAX_SUM，使得每个人的工作量 <= MAX_SUM
# 每个需求只能由一个开发人员独立完成，因此 max(works) - 1 一定不可能是有效的解
l, r = max(works) - 1, sum(works)
while l + 1 < r:
    mid = (l + r) >> 1
    if ok(0, mid, [0] * N):
        r = mid
    else:
        l = mid
print(r)

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstring>

using namespace std;

int N, wlen = 0;
int sums[10 + 5];
int works[30 + 5];


bool ok(int idx, const int MAX_SUM) {
    if (idx == wlen) {
        return true;
    }

    for (int i = 0; i < N; i++) {
        // 尝试将 idx 个工作分配给第 i 个人员
        if (sums[i] + works[idx] <= MAX_SUM) {
            sums[i] += works[idx];
            if (ok(idx + 1, MAX_SUM)) {
                return true;
            }
            sums[i] -= works[idx];
        }
    }

    return false;
}

int main() {
    // 读取每个工作的工作量
    while(cin >> works[wlen++]) {
        if(cin.peek() == '\n') break;
    }

    // 读取开发人员的数量
    cin >> N;

    // 二分查找，找到最小的 MAX_SUM，使得每个人的工作量 <= MAX_SUM
    int l = *max_element(works, works + wlen) - 1;
    int r = accumulate(works, works + wlen, 0);
    while (l + 1 < r) {
        int mid = (l + r) >> 1;
        memset(sums, 0, sizeof(sums));
        if (ok(0, mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }

    cout << r << endl;

    return 0;
}