【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试之【二分查找】2023C-项目排期【欧弟算法】全网注释最详细分类最全的华为OD真题题解

���LeetCode算法/华为OD考试扣扣交流群可加 948025485

可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题

绿色聊天软件戳 od1336了解算法冲刺训练

文章目录

• 题目描述与示例
• • 题目描述
  • 输入描述
  • 输出描述
  • 示例
  • • 输入
    • 输出
    • 说明
    • 解题思路
    • 代码
    • • python
      • java
      • cpp
      • 时空复杂度
      • 华为OD算法/大厂面试高频题算法练习冲刺训练

        题目描述与示例

        题目描述

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

        输入描述

        第一行输入为M个需求的工作量，单位为天，用逗号隔开。

        例如：X1 X2 X3 … Xm 。表示共有M个需求，每个需求的工作量分别为X1天，X2天…Xm天。

        其中0

        第二行输入为项目组人员数量N

        输出描述

        最快完成所有工作的天数

        示例

        输入

        6 2 7 7 9 3 2 1 3 11 42

        输出

        28

        说明

        共有两位员工，其中一位分配需求 6 2 7 7 3 2 1 共需要28天完成，另一位分配需求 9 3 11 4 共需要27天完成，故完成所有工作至少需要28天。

        解题思路

        又是一道描述相当晦涩的题目（很想骂人）

        用比较简洁的数学语言来描述就是，将数组X1, X2, X3, ... ,Xm分为N部分（并非子数组，不要求连续），设每一部分的和为sum1, sum2, ..., sumN，要求找到一种分配方式使得max(sum1, sum2, ..., sumN)最小。

        用一句简单的话来说，就是最小化各部分求和的最大值。这种设问一定要想到用二分来完成。

        将问题转化为，我们需要找到一个阈值k（一个人的最大工作量），并将原数组nums可以被分为N部分（分配给N个人），使得这N部分的各自求和的最大值都不会超过k（每个人各自的工作量不会超过k）。

        显然k的选择是一个二段性问题：

        • 当k非常大时，原数组nums无论如何分配都可以完成要求
        • 当k非常小时，原数组nums无论怎么分配都无法完成要求
        • 必然存在一个临界值k，使得存在nums的分配结果恰好完成要求。

          我们希望找到这个阈值k，因此需要对k进行二分查找，二分查找的范围为[max(nums), sum(nums)]。当

          • k = max(nums)时，能够被分为m = len(nums)部分（需要m个人来完成所有工作）
          • k = sum(nums)时，能够被分为1部分（只由1个人可以完成所有工作）

            而上述二分过程的贪心子问题为：当我们选择了阈值k时，数组nums能否被分割不超过N部分？

            这个问题就和【贪心】2023B-数据最节约的备份方法几乎完全一致了，其代码为

             def sub_question(k, nums, m, N):    ans = 0    check = [0] * m    for i in range(m):        if check[i] == 1:            continue        ans += 1        cur_sum = 0        j = i        while j  k:                j += 1            else:                cur_sum += nums[j]                check[j] = 1                j += 1    return ans  k:                j += 1            # 如果第j份工作和当前员工之前的工作量之和不超过k            # 则贪心地将这份工作安排给这个员工            # 修改cur_sum和check[j]，j递增            else:                cur_sum += nums[j]                check[j] = 1                j += 1    # 退出循环时，如果需要的人数ans不超过N，则返回True，否则返回False    return ans     // 贪心子问题    private static boolean subQuestion(int k, int[] nums, int m, int N) {        int ans = 0;        int[] check = new int[m];        for (int i = 0; i  num) {        nums.push_back(num);    }    int m = nums.size();    int N;    cin >> N;    sort(nums.begin(), nums.end(), greater());    int left = nums[0], right = accumulate(nums.begin(), nums.end(), 0) + 1;    while (left