最新华为OD机试真题-项目排期安排(200分)
🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员
💻 ACM金牌🏅️团队 ｜ 编程一对一辅导
✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解
👏 感谢大家的订阅➕ 和 喜欢💗 和手里的小花花🌸
最新华为OD机试D卷目录，全、新、准，题目覆盖率达 95% 以上，支持题目在线评测
最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users
📎 在线评测链接
🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～
🍓OJ题目截图
🍏 项目排期安排
问题描述
项目组共有 个开发人员，项目经理接到了
个独立的需求。每个需求的工作量不同，且每个需求只能由一个开发人员独立完成，不能多人合作。假定各个需求之间无任何先后依赖关系，设计算法帮助项目经理进行工作安排，使整个项目能用最少的时间交付。
输入格式
第一行输入为 个需求的工作量，单位为天，用空格隔开。例如：
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天。
数据范围
题解
本题可以通过二分查找来确定最少的天数。先对工作量进行降序排序，然后采用二分法来查找最短的时间。
- 确定时间的上下界，上界是所有工作量的总和，下界是最小的工作量。
- 在每次二分查找中，检查是否可以在当前的天数限制下完成所有任务。如果可以，说明还可以缩短时间；如果不可以，说明需要更多时间。
- 通过递归分配任务给员工来判断当前时间限制是否可行。
参考代码
- 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 剩余60%内容，订阅专栏后可继续查看/也可单篇购买
最新华为OD机试-E+D卷 文章被收录于专栏
本专栏给大家提供了华为2024最新华为OD-E/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 部分题目提供OJ在线评测
查看9道真题和解析
投递华为等公司10个岗位 >