一、题目 §
部门在进行需求开发时需要进行人力安排。
当前部门需要完成 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
三、输出 §
对于每一组测试数据，输出部门需要人力需求，
行末无多余的空格。
四、示例 §
输入：
3
3 5 3 4
输出：
6
说明：
输入数据两行，
第一行输入数据 3 表示开发时间要求
第二行输入数据表示需求工作量大小，
输出数据一行，表示部门人力需求。
当选择人力为6时，2个需求量为3的工作
可以在1个月里完成，其他2个工作
各需要1个月完成。可以在3个月内完成所有需求。
当选择人力为5时，4个工作各需要1个月完成，
一共需要4个月才能完成所有需求。
因此6是部门最小的人力需求。
五、题解 §
- 答案具有单调性并且可以锁定在一个区间范围内，
容易想到使用二分法
- 区间：
- 开始值：耗费人力最大的一个需求。
一个需求必须在一个月内完成，
这个隐含的需求题目中没有说清楚，
但是对最后的答案有影响，容易忽略
- 结束值：耗费人力最大和次大的
2 个需求之和。因为题目规定每个月
最多只能完成 2 个需求
5.1 Java 实现 §
package org.stone.study.algo.ex202411;
import java.util.Arrays;
import java.util.Scanner;
/**
* 部门人力分配
*/
public class ManPowerAllocation {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = Integer.parseInt(scanner.nextLine());
String[] strArr = scanner.nextLine().split(" ");
int[] requirements = Arrays.stream(strArr).mapToInt(Integer::parseInt).toArray();
int ans = allocateManPower(m, requirements);
System.out.println(ans);
}
/**
*
* @param m: 完成所有任务的工期
* @param requirements
* @return
*/
public static int allocateManPower(int m, int[] requirements) {
Arrays.sort(requirements);
int n = requirements.length;
int left = requirements[n-1]; // 最小的工作量：每月至少完成一个需求（不能一个需求拆分为 2 个月内完成）
int right = requirements[n-1] + requirements[n-2]; // 最大的工作量:每月最多完成 2 个需求
int ans = right;
while (left <= right) {
int mid = left + (right - left) / 2;
if (check(m, requirements, mid)) {
ans = mid; // 满足条件，尝试更小的工作量
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
/**
*
* @param m: 完成所有任务要求的月数
* @param requirements
* @param maxWorkload：待试探的每个月的工作量或者人力
* @return
*/
public static boolean check(int m, int[] requirements, int maxWorkload) {
int left = 0;
int right = requirements.length - 1;
// 实际花费的月数
int needs = 0;
while (left <= right) {
if (requirements[left] + requirements[right] <= maxWorkload) {
left++;
right--;
} else {
right--;
}
++needs;
}
return needs <= m;
}
}
5.2 Python实现 §
# 二分查找 找可行解和最优解
def allocatManPower(m: int, requirements: list[int]) -> int:
sorted(requirements)
left, right = requirements[-1], requirements[-1] + requirements[-2]
while left < right:
mid = (left + right) // 2
if check(mid, requirements, m):
right = mid
else:
left = mid + 1
return left
# 按 mid 分配人力，是否满足m个月完成所有需求。采用贪心和双指针思路，优先分配一个大的需求+一个小的需求
def check(mid: int, requirements: list[int], m: int) -> bool:
needs = 0
left, right = 0, len(requirements) - 1
while left <= right:
if requirements[left] + requirements[right] <= mid:
left += 1
right -= 1
else:
right -= 1
needs += 1
return needs <= m
if __name__ == "__main__":
# 3
m = int(input())
# 3 5 3 4
requirements = list(map(int, input().split()))
# 6
print(allocatManPower(m, requirements))