华为OD机试 - 项目排期 - 二分查找、回溯（Python/JS/C/C++ 2024 D卷 200分）

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。

一、题目描述

项目组共有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：

1、输入

8 8 8 8 8 1
3

2、输出

测试用例1：

1、输入

10 10 10 10
2

2、输出

3、说明

两名员工各分配两项任务，最大负载为20天。

五、解题思路

二分查找结合回溯的方法能够高效地在可能的天数范围内找到最小的可行天数。

排序：首先将任务按降序排序，以便优先分配工作量较大的任务。
二分查找：
- 左边界：最大单个任务的工作量（至少需要这么多天）。
- 右边界：所有任务的总和（最多需要这么多天）。
- 中间值：尝试将任务分配到员工，使得每个员工的总负载不超过中间值。
回溯（DFS）：
- 尝试将每个任务分配给不同的员工，确保不超过当前的目标天数。
- 如果所有任务都能被分配，调整右边界；否则，调整左边界。
迭代：通过不断缩小搜索范围，最终找到最小的可行天数。

六、Python算法源码

python">def calculate_minimum_days(workloads, num_employees):# 将任务按降序排序workloads.sort(reverse=True)# 定义二分查找的左右边界left = workloads[0]  # 最大单个任务的工作量right = sum(workloads)  # 所有任务的总和def can_complete(workloads, num_employees, target, index, employee_load):if index == len(workloads):return True  # 所有任务已分配current_task = workloads[index]for i in range(num_employees):if employee_load[i] + current_task > target:continue  # 当前员工无法承载此任务if i > 0 and employee_load[i] == employee_load[i - 1]:continue  # 避免重复分配相同负载的员工employee_load[i] += current_task  # 分配任务if can_complete(workloads, num_employees, target, index + 1, employee_load):return True  # 成功分配所有任务employee_load[i] -= current_task  # 回溯return False  # 无法分配while left < right:mid = left + (right - left) // 2  # 计算中间值employee_load = [0] * num_employees  # 初始化员工负载if can_complete(workloads, num_employees, mid, 0, employee_load):right = mid  # 尝试更小的天数else:left = mid + 1  # 增加天数return left  # 最小可行天数def main():import systry:# 读取工作量workloads_line = sys.stdin.readline()workloads = list(map(int, workloads_line.strip().split()))if not (0 < len(workloads) < 30):print("输入的任务数量不符合要求")returnfor w in workloads:if not (0 < w < 200):print("输入的任务工作量不符合要求")return# 读取员工数量n_line = sys.stdin.readline()num_employees = int(n_line.strip())if not (0 < num_employees < 10):print("输入的员工数量不符合要求")returnmin_days = calculate_minimum_days(workloads, num_employees)print(min_days)except:print("输入格式错误")if __name__ == "__main__":main()

七、JavaScript算法源码

javascript">function calculateMinimumDays(workloads, numEmployees) {// 将任务按降序排序workloads.sort((a, b) => b - a);// 定义二分查找的左右边界let left = workloads[0]; // 最大单个任务的工作量let right = workloads.reduce((a, b) => a + b, 0); // 所有任务的总和// 回溯函数，尝试分配任务function canComplete(workloads, numEmployees, target, index, employeeLoad) {if (index === workloads.length) {return true; // 所有任务已分配}let currentTask = workloads[index];for (let i = 0; i < numEmployees; i++) {if (employeeLoad[i] + currentTask > target) {continue; // 当前员工无法承载此任务}if (i > 0 && employeeLoad[i] === employeeLoad[i - 1]) {continue; // 避免重复分配相同负载的员工}employeeLoad[i] += currentTask; // 分配任务if (canComplete(workloads, numEmployees, target, index + 1, employeeLoad)) {return true; // 成功分配所有任务}employeeLoad[i] -= currentTask; // 回溯}return false; // 无法分配}while (left < right) {let mid = Math.floor(left + (right - left) / 2); // 计算中间值let employeeLoad = Array(numEmployees).fill(0); // 初始化员工负载if (canComplete(workloads, numEmployees, mid, 0, employeeLoad)) {right = mid; // 尝试更小的天数} else {left = mid + 1; // 增加天数}}return left; // 最小可行天数
}function main() {const fs = require('fs');const input = fs.readFileSync('/dev/stdin', 'utf8').trim().split('\n');try {// 读取工作量let workloads = input[0].trim().split(/\s+/).map(Number);if (!(workloads.length > 0 && workloads.length < 30)) {console.log("输入的任务数量不符合要求");return;}for (let w of workloads) {if (!(w > 0 && w < 200)) {console.log("输入的任务工作量不符合要求");return;}}// 读取员工数量let numEmployees = parseInt(input[1].trim());if (!(numEmployees > 0 && numEmployees < 10)) {console.log("输入的员工数量不符合要求");return;}let minDays = calculateMinimumDays(workloads, numEmployees);console.log(minDays);} catch (err) {console.log("输入格式错误");}
}main();

八、C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 比较函数，用于qsort，降序排序
int compare(const void *a, const void *b) {return (*(int*)b - *(int*)a);
}// 回溯函数，尝试分配任务
int canComplete(int workloads[], int m, int numEmployees, int target, int index, int employeeLoad[]) {if (index == m) {return 1; // 所有任务已分配}int currentTask = workloads[index];for (int i = 0; i < numEmployees; i++) {if (employeeLoad[i] + currentTask > target) {continue; // 当前员工无法承载此任务}if (i > 0 && employeeLoad[i] == employeeLoad[i - 1]) {continue; // 避免重复分配相同负载的员工}employeeLoad[i] += currentTask; // 分配任务if (canComplete(workloads, m, numEmployees, target, index + 1, employeeLoad)) {return 1; // 成功分配所有任务}employeeLoad[i] -= currentTask; // 回溯}return 0; // 无法分配
}// 计算最短完成时间
int calculateMinimumDays(int workloads[], int m, int numEmployees) {// 将任务按降序排序qsort(workloads, m, sizeof(int), compare);// 定义二分查找的左右边界int left = workloads[0]; // 最大单个任务的工作量int right = 0;for(int i = 0; i < m; i++) {right += workloads[i]; // 所有任务的总和}while (left < right) {int mid = left + (right - left) / 2; // 计算中间值int employeeLoad[numEmployees];memset(employeeLoad, 0, sizeof(employeeLoad)); // 初始化员工负载if (canComplete(workloads, m, numEmployees, mid, 0, employeeLoad)) {right = mid; // 尝试更小的天数} else {left = mid + 1; // 增加天数}}return left; // 最小可行天数
}int main() {char workloadInput[1000];// 读取工作量if (fgets(workloadInput, sizeof(workloadInput), stdin) == NULL) {printf("输入格式错误\n");return 0;}// 分割工作量字符串int workloads[30];int m = 0;char *token = strtok(workloadInput, " \n");while (token != NULL && m < 30) {workloads[m++] = atoi(token);token = strtok(NULL, " \n");}// 检查任务数量if (!(m > 0 && m < 30)) {printf("输入的任务数量不符合要求\n");return 0;}// 检查每个任务的工作量for(int i = 0; i < m; i++) {if (!(workloads[i] > 0 && workloads[i] < 200)) {printf("输入的任务工作量不符合要求\n");return 0;}}// 读取员工数量int numEmployees;if (scanf("%d", &numEmployees) != 1) {printf("输入格式错误\n");return 0;}if (!(numEmployees > 0 && numEmployees < 10)) {printf("输入的员工数量不符合要求\n");return 0;}int minDays = calculateMinimumDays(workloads, m, numEmployees);printf("%d\n", minDays);return 0;
}

九、C++算法源码

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;// 回溯函数，尝试分配任务
bool canComplete(vector<int> &workloads, int m, int numEmployees, int target, int index, vector<int> &employeeLoad) {if (index == m) {return true; // 所有任务已分配}int currentTask = workloads[index];for (int i = 0; i < numEmployees; i++) {if (employeeLoad[i] + currentTask > target) {continue; // 当前员工无法承载此任务}if (i > 0 && employeeLoad[i] == employeeLoad[i - 1]) {continue; // 避免重复分配相同负载的员工}employeeLoad[i] += currentTask; // 分配任务if (canComplete(workloads, m, numEmployees, target, index + 1, employeeLoad)) {return true; // 成功分配所有任务}employeeLoad[i] -= currentTask; // 回溯}return false; // 无法分配
}// 计算最短完成时间
int calculateMinimumDays(vector<int> &workloads, int numEmployees) {// 将任务按降序排序sort(workloads.begin(), workloads.end(), greater<int>());// 定义二分查找的左右边界int left = workloads[0]; // 最大单个任务的工作量int right = 0;for(auto w : workloads) {right += w; // 所有任务的总和}while (left < right) {int mid = left + (right - left) / 2; // 计算中间值vector<int> employeeLoad(numEmployees, 0); // 初始化员工负载if (canComplete(workloads, workloads.size(), numEmployees, mid, 0, employeeLoad)) {right = mid; // 尝试更小的天数} else {left = mid + 1; // 增加天数}}return left; // 最小可行天数
}int main(){ios::sync_with_stdio(false);cin.tie(0);// 读取工作量string workloadInput;if (!getline(cin, workloadInput)) {cout << "输入格式错误" << endl;return 0;}// 分割工作量字符串vector<int> workloads;int w;int pos = 0;while (pos < workloadInput.size()) {while (pos < workloadInput.size() && workloadInput[pos] == ' ') pos++;if (pos >= workloadInput.size()) break;int start = pos;while (pos < workloadInput.size() && workloadInput[pos] != ' ') pos++;w = stoi(workloadInput.substr(start, pos - start));workloads.push_back(w);}// 检查任务数量if (!(workloads.size() > 0 && workloads.size() < 30)) {cout << "输入的任务数量不符合要求" << endl;return 0;}// 检查每个任务的工作量for(auto task : workloads) {if (!(task > 0 && task < 200)) {cout << "输入的任务工作量不符合要求" << endl;return 0;}}// 读取员工数量int numEmployees;if (!(cin >> numEmployees)) {cout << "输入格式错误" << endl;return 0;}if (!(numEmployees > 0 && numEmployees < 10)) {cout << "输入的员工数量不符合要求" << endl;return 0;}int minDays = calculateMinimumDays(workloads, numEmployees);cout << minDays << "\n";return 0;
}