刷题笔记合集🔗

项目排期

问题描述

项目组共有 个开发人员，项目经理接到了 个独立的需求。每个需求的工作量不同，且每个需求只能由一个开发人员独立完成，不能多人合作。假定各个需求之间无任何先后依赖关系，设计算法帮助项目经理进行工作安排，使整个项目能用最少的时间交付。

输入格式

第一行输入为 个需求的工作量，单位为天，用空格隔开。例如：

6 2 7 7 9 3 2 1 3 11 4

表示共有 个需求，每个需求的工作量分别为 天， 天， 天， 天， 天， 天， 天， 天， 天， 天， 天。其中 ，。

第二行输入为项目组人员数量 ，例如：

2

表示共有 名员工，其中 。

输出格式

输出整个项目最快完成的天数。

样例输入

6 2 7 7 9 3 2 1 3 11 4
2

样例输出

28

样例解释

在样例中，需求可以分配如下：

• 开发人员1：6 + 7 + 9 + 3 + 3 = 28 天
• 开发人员2：2 + 7 + 2 + 1 + 11 + 4 = 27 天

所以，最快完成所有工作的天数为28天。

数据范围

题解

本题可以通过二分查找来确定最少的天数。先对工作量进行降序排序，然后采用二分法来查找最短的时间。

1. 确定时间的上下界，上界是所有工作量的总和，下界是最小的工作量。
2. 在每次二分查找中，检查是否可以在当前的天数限制下完成所有任务。如果可以，说明还可以缩短时间；如果不可以，说明需要更多时间。
3. 通过递归分配任务给员工来判断当前时间限制是否可行。

参考代码

• Python

def min_days_to_complete(work_lst, n):
    work_lst.sort(reverse=True)
    m = len(work_lst)
    total_hours = sum(work_lst)

    def check(days, count, people_work_lst):
        if count == m:
            return True
        for i in range(n):
            if work_lst[count] + people_work_lst[i] <= days:
                people_work_lst[i] += work_lst[count]
                if check(days, count + 1, people_work_lst):
                    return True
                people_work_lst[i] -= work_lst[count]
        return False

    l, r = 1, total_hours
    while l < r:
        mid = (l + r) // 2
        if check(mid, 0, [0] * n):
            r = mid
        else:
            l = mid + 1

    return l

if __name__ == "__main__":
    work_lst = list(map(int, input().split()))
    n = int(input())
    print(min_days_to_complete(work_lst, n))

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] workLst = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = sc.ne