最新华为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%内容,订阅专栏后可继续查看/也可单篇购买
本专栏给大家提供了华为2024最新华为OD-E/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 部分题目提供OJ在线评测