项目排期 - 华为OD统一考试（C卷）
OD统一考试（C卷）
分值： 200分
题解： Java / Python / C++
题目描述
项目组共有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;
}
🙏整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏
#面经##秋招##春招##校招##华为#
查看16道真题和解析
