欢迎光临
我们一直在努力

33.华为 OD-C 卷 200 分题目 5 - 项目排期(Java 实现)

📝 题目描述

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

输入格式

• 第一行输入为 M 个需求的工作量,单位为天,用逗号或空格隔开。例如:X1 X2 X3 … Xm,表示共有 M 个需求,每个需求的工作量分别为 X1 天,X2 天…Xm 天。 ◦ 约束:0 < M < 30;0 < Xm < 200 • 第二行输入为项目组人员数量 N

输出格式

输出最快完成所有工作的天数

样例输入

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 天。

💡 解题思路

这是一个典型的最小化最大负载问题,属于 NP 难问题,我们可以用二分查找 + 贪心验证的思路高效解决:

1. 确定二分边界:

◦ 下界 left:需求中工作量最大的天数(单个需求必须由一个人完成,所以总时间至少不小于最大的单个需求) ◦ 上界 right:所有需求工作量之和(只有一个人时的总时间)

2. 二分查找最小时间:

◦ 取中间值 mid,判断是否能在 mid

赞(0)
未经允许不得转载:171主机测评 » 33.华为 OD-C 卷 200 分题目 5 - 项目排期(Java 实现)
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址