部门人力分配 - 华为OD统一考试

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

alt

题目描述

部门在进行需求开发时需要进行人力安排。当前部门需要完成 N 个需求，需求用 requirements[i] 表示，requirements[i] 表示第 i 个需求的工作量大小，单位：人月。这部分需求需要在 M 个月内完成开发，进行人力安排后每个月的人力是固定的。

目前要求每个月最多有 2 个需求开发，并且每个月需要完成的需求不能超过部门人力。请帮部门评估在满足需求开发进度的情况下，每个月需要的最小人力是多少。

输入描述

输入第一行为 M ，第二行为 requirements 。

M 表示需要开发时间要求，requirements 表示每个需求工作量大小， N 为 requirements 长度。

1 ≤ N / 2 ≤ M ≤ N ≤ 10000，1 ≤ requirements[i]≤ 10^9

输出描述

对于每一组测试数据，输出部门需要人力需求，行末无多余的空格。

示例1

输入：
3
3 5 3 4输出：
6说明：
输入数据两行，第一行输入数据 3 表示开发时间要求，第二行输入数据表示需求工作量大小，输出数据一行，表示部门人力需求。 
当选择人力为6时，2个需求量为3的工作可以在1个月里完成，其他2个工作各需要1个月完成。可以在3个月内完成所有需求。 
当选择人力为5时，4个工作各需要1个月完成，一共需要4个月才能完成所有需求。 
因此6是部门最小的人力需求。

题解

这是一个二分算法 + 贪心的题目。题目要求在 M 个月内完成 N 个需求，每个月最多完成 2 个需求，且每个月需要完成的需求不能超过部门人力。我们需要求解每个月所需的最小人力，以满足需求开发进度。

解题思路：

对需求的工作量进行排序。
使用二分查找确定每个月所需的最小人力。
在二分查找的过程中，通过贪心策略，尽可能每个月完成 2 个需求，从而在 M 个月内完成尽量多的需求。
如果当前人力能够满足在 M 个月内完成所有需求，则减小人力；否则增大人力。

Java

import java.util.Arrays;
import java.util.Scanner;
/*** @author code5bug*/
public class Main {// 判断每个月需要的最小人力 power ，能否在 M 个月内完成开发public static boolean check(int[] requirements, long power, int M) {int months = 0;int l = 0, r = requirements.length - 1;while (l <= r) {// 【贪心】如果每个月可以完成 2 个则完成 2 个if (requirements[l]  <= power - requirements[r]) {l++;}r--;months++;}return months <= M;}public static void main(String[] args) {Scanner in = new Scanner(System.in);int M = Integer.parseInt(in.nextLine());int[] requirements = Arrays.stream(in.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();Arrays.sort(requirements);// 由于每个月需要完成的需求不能超过部门人力， 因此最小的部门人力为 max(requirements)long l = Arrays.stream(requirements).max().getAsInt() - 1;long r = Arrays.stream(requirements).asLongStream().sum();while (l + 1 < r) {long mid = (l + r) / 2;if (check(requirements, mid, M)) {r = mid;} else {l = mid;}}System.out.println(r);}
}

Python

from typing import Listdef check(requirements: List[int], power: int) -> bool:"""判断每个月需要的最小人力 power ，能否在 M 个月内完成开发"""global Mmonths = 0l, r = 0, len(requirements) - 1while l <= r:if requirements[l] <= power - requirements[r]: # 【贪心】如果每个月可以完成 2 个则完成2个l += 1r -= 1months += 1return months <= Mif __name__ == '__main__':M = int(input())requirements = list(map(int, input().split()))requirements.sort()l, r = max(requirements) - 1, sum(requirements)while l + 1 < r:mid = (l + r) // 2if check(requirements, mid):r = midelse:l = mid

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>using namespace std;int M;// 判断每个月需要的最小人力 power ，能否在 M 个月内完成开发
bool check(vector<int>& requirements, long long power) {int months = 0;int l = 0, r = requirements.size() - 1;while (l <= r) {// 【贪心】如果每个月可以完成 2 个则完成 2 个if (requirements[l] <= power - requirements[r]) {l++;}r--;months++;}return months <= M;
}int main() {cin >> M;vector<int> requirements;int requirement;while (cin >> requirement) {requirements.push_back(requirement);}sort(requirements.begin(), requirements.end());long long l = *max_element(requirements.begin(), requirements.end()) - 1;long long r = accumulate(requirements.begin(), requirements.end(), 0LL);while (l + 1 < r) {long mid = (l + r) / 2;if (check(requirements, mid)) {r = mid;} else {l = mid;}}cout << r << endl;return 0;
}