最新华为OD机试真题-部门项目任务分配(100分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

=> 部门项目任务分配(100分) <=

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

🍌 部门项目任务分配

问题描述

卢小姐所在的部门正在进行项目开发，需要在 个月内完成 个任务。每个任务的工作量用 表示，单位为人月。为了提高效率，部门要求每个月最多同时进行 个任务，且每个月完成的任务总工作量不能超过该月的人力资源数。请帮助卢小姐确定在满足任务开发进度要求的情况下，每个月所需的最小人力资源数。

输入格式

第一行包含一个整数 ，表示项目开发时间。

第二行包含 个空格分隔的整数 ，表示每个任务的工作量。

输出格式

输出一个整数，表示每个月所需的最小人力资源数。

样例输入

3
3 5 3 4

样例输出

6

数据范围

题解

本题可以使用二分答案的思路来解决。可以将每个月的人力资源数二分枚举，判断当前枚举的人力资源数是否满足任务开发的要求。

具体步骤如下：

1. 将任务工作量数组 按照从小到大排序。

2. 二分枚举人力资源数的范围，左端点为 中的最大值，右端点为 。

3. 对于每个枚举的人力资源数 ，使用双指针判断是否满足任务开发要求：

   • 初始化左右指针 和 分别指向 的左右端点。
   • 如果 ，表示当前两个任务可以在同一个月完成，将左指针右移，右指针左移。
   • 否则，只能完成右指针指向的任务，将右指针左移。
   • 每次指针移动，计数器 加 ，表示需要的月数。
   • 如果 ，说明当前枚举的人力资源数满足要求，缩小右端点；否则，增大左端点。

4. 二分结束后，左端点即为所需的最小人力资源数。

时间复杂度为 ，空间复杂度为 。

参考代码

• Python

def check(x):
    cnt = 0
    l, r = 0, n - 1
    while l <= r:
        if tasks[l] + tasks[r] <= x:
            l += 1
            r -= 1
        else:
            r -= 1
        cnt += 1
    return cnt <= m

m = int(input())
tasks = list(map(int, input().split()))
n = len(tasks)
tasks.sort()

left, right = tasks[-1], 10**9
while left < right:
    mid = left + right >> 1
    if check(mid):
        right = mid
    else:
        left = mid + 1

print(left)

• Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static final int N = 10005;
    static int n, m;
    static int[] tasks = new int[N];

    public static boolean check(int x) {
        int cnt = 0;
        int l = 0, r = n - 1;
        while (l <= r) {
            if (tasks[l] + tasks[r] <= x) {
                l++;
                r--;
            } else {
                r--;
            }
            cnt++;
        }
        return cnt <= m;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        m = scanner.nextInt();
        while (scanner.hasNext()) {
            tasks[n++] = scanner.nextInt();
        }
        Arrays.sort(tasks, 0, n);

        int left = tasks[n - 1], right = (int) 1e9;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (check(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        System.out.println(left);
    }
}

• Cpp

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e4 + 5;
int n, m;
int tasks[N];

bool check(int x) {
    int cnt = 0;
    int l = 0, r = n - 1;
    while (l <= r) {
        if (tasks[l] + tasks[r] <= x) {
            l++;
            r--;
        } else {
            r--;
        }
        cnt++;
    }
    return cnt <= m;
}

int main() {
    cin >> m;
    while (cin >> tasks[n]) n++;
    sort(tasks, tasks + n);

    int left = tasks[n - 1], right = 1e9;
    while (left < right) {
        int mid = left + right >> 1;
        if (check(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    cout << left << endl;
    return 0;
}