江苏省建设厅网站建造师栏,linux服务器WordPress建站教程,python 网站开发书籍,pc端百度OD统一考试#xff08;C卷#xff09; 分值#xff1a; 200分 题解#xff1a; Java / Python / C 题目描述
项目组共有N个开发人员#xff0c;项目经理接到了M个独立的需求#xff0c;每个需求的工作量不同#xff0c;且每个需求只能由一个开发人员独立完成#xff0… OD统一考试C卷 分值 200分 题解 Java / Python / C 题目描述
项目组共有N个开发人员项目经理接到了M个独立的需求每个需求的工作量不同且每个需求只能由一个开发人员独立完成不能多人合作。
假定各个需求直接无任何先后依赖关系请设计算法帮助项目经理进行工作安排使整个项目能用最少的时间交付。
输入描述
第一行输入为M个需求的工作量单位为天用逗号隔开。 例如X1 X2 X3 … Xm 表示共有M个需求每个需求的工作量分别为X1天X2天…Xm天。其中0M300Xm200 第二行输入为项目组人员数量N 例如 5 表示共有5名员工其中0N10
输出描述
最快完成所有工作的天数 例如 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_SUMint 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_SUMprivate 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)) { // 可以完成分配则直接返回 truereturn true;}sums[i] - works[idx];}}return false;}
}Python
from typing import Listworks 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_SUMglobal Nif idx len(works):return Truefor 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 Truesums[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) 1if ok(0, mid, [0] * N):r midelse:l mid
print(r)
C
#include iostream
#include vector
#include algorithm
#include numeric
#include cstringusing 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_SUMint 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;
} ❤️华为OD机试面试交流群每日真题分享 加V时备注“华为od加群” 整理题解不易 如果有帮助到您请给点个赞 ❤️ 和收藏 ⭐让更多的人看到。
