- 部门人力分配（Java JS Python C）)
(100分)- 部门人力分配（Java & JS & Python & C）
题目描述
部门在进行需求开发时需要进行人力安排。
当前部门需要完成 N 个需求，需求用 requirements 表述，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是部门最小的人力需求。 |
题目解析
本题是将二分和双指针考点结合在了一起。
本题我们可以换个说法：
目前有 N 个人（N个需求），
每个人的体重为requirements[i]，（每个需求开发需要的人力为requirements[i]）
以及 M 辆自行车（M个月开发），
每辆自行车至多坐两人（每个月至多开发两个需求），
现在想要用 M 辆自行车带走 N 个人，问每辆自行车的限重至少是多少？（M个月开发完N个需求，每个月至少需要多少人力）
每辆自行车载重：
- min 至少是 1st_max(requirements)，这样才能保证最重的人可以单独骑一辆自行车
- max 至多是 1st_max(requirements) + 2nd_max(requirements)，这样最重的两个人可以骑在一辆自行车商
我们可以在该[min, max]范围内二分找中间值mid，作为每辆自行车的限重去尝试（check）,看对应限重下至少需要多少辆自行车。
比如二分取中间值mid作为每辆自行车的限重，并将体重数组requirements升序排序，定义两个指针L，R，初始化L = 0，R=requirements.length -1。
那么L指向的就是体重最轻的人，R指向的就是体重最重的人。
- 如果 requirement[L] + requirement[R] <= mid，则说明最轻的人和最重的人可以坐一辆自行车，然后L++，R--，用车数量 need++
- 如果 requirement[L] + requirement[R] > mid，则说明最重的人只能一个人坐一辆自行车，无法搭配其他人，然后仅 R-- ，用车数量 need++
按上面逻辑继续进行，直到L > R时，即所有人都坐上了自行车时停止，此时我们比较need和M，
- 如果need <= M，则说明 mid 限重可以满足M辆车带走所有人，此时mid就是一个本题的一个可能解，但不一定时最优解，我们应该继续尝试更小的限重，即max = mid - 1
- 如果need > M，则说明 mid 限重无法满足M辆车带走所有人，因此我们需要更大的限重，即 min = mid + 1
然后继续二分取中间值作为限重带入前面双指针逻辑check。
另外本题需要注意整型溢出问题。
JS算法源码
const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; // 输入处理 void (async function () { const m = parseInt(await readline()); const requirements = (await readline()).split(" ").map(Number); console.log(getResult(m, requirements)); })(); function getResult(m, requirements) { requirements.sort((a, b) => a - b); const n = requirements.length; // 每辆自行车的限重 至少是 最重的那个人的体重 let min = requirements[n - 1]; // 每辆自行车的限重 至多是 最重的和次重的那两个的体重 let max = requirements[n - 2] + requirements[n - 1]; let ans = max; // 二分取中间值 while (min <= max) { const mid = Math.floor((min + max) / 2); // 注意这里不能使用 >> 1 运算，会出现整型溢出 if (check(mid, m, requirements)) { // 如果mid限重，可以满足m辆车带走n个人，则mid就是一个可能解，但不一定是最优解 ans = mid; // 继续尝试更小的限重，即缩小右边界 max = mid - 1; } else { // 如果mid限重，不能满足m辆车带走n个人，则mid限重小了，我们应该尝试更大的限重，即扩大左边界 min = mid + 1; } } return ans; } /** * @param limit 每辆自行车的限重 * @param m m辆自行车 * @param requirements n个人的体重数组 * @return m辆自行车，每辆限重limit的情况下，能否带走n个人 */ function check(limit, m, requirements) { let l = 0; // 指向体重最轻的人 let r = requirements.length - 1; // 指向体重最重的人 // 需要的自行车数量 let need = 0; while (l <= r) { // 如果最轻的人和最重的人可以共享一辆车，则l++,r--， // 否则最重的人只能单独坐一辆车，即仅r-- if (requirements[l] + requirements[r] <= limit) { l++; } r--; // 用掉一辆车 need++; } // 如果m >= need，当前有的自行车数量足够 return m >= need; }Java算法源码
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = Integer.parseInt(sc.nextLine()); int[] requirements = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray(); System.out.println(getResult(m, requirements)); } public static long getResult(int m, int[] requirements) { Arrays.sort(requirements); int n = requirements.length; // 每辆自行车的限重 至少是 最重的那个人的体重 long min = requirements[n - 1]; // 每辆自行车的限重 至多是 最重的和次重的那两个的体重 long max = requirements[n - 2] + requirements[n - 1]; long ans = max; // 二分取中间值 while (min <= max) { long mid = (min + max) >> 1; // 需要注意的是，min，max单独看都不超过int，但是二者相加会超过int，因此需要用long类型 if (check(mid, m, requirements)) { // 如果mid限重，可以满足m辆车带走n个人，则mid就是一个可能解，但不一定是最优解 ans = mid; // 继续尝试更小的限重，即缩小右边界 max = mid - 1; } else { // 如果mid限重，不能满足m辆车带走n个人，则mid限重小了，我们应该尝试更大的限重，即扩大左边界 min = mid + 1; } } return ans; } /** * @param limit 每辆自行车的限重 * @param m m辆自行车 * @param requirements n个人的体重数组 * @return m辆自行车，每辆限重limit的情况下，能否带走n个人 */ public static boolean check(long limit, int m, int[] requirements) { int l = 0; // 指向体重最轻的人 int r = requirements.length - 1; // 指向体重最重的人 // 需要的自行车数量 int need = 0; while (l <= r) { // 如果最轻的人和最重的人可以共享一辆车，则l++,r--， // 否则最重的人只能单独坐一辆车，即仅r-- if (requirements[l] + requirements[r] <= limit) { l++; } r--; // 用掉一辆车 need++; } // 如果m >= need，当前有的自行车数量足够 return m >= need; } }Python算法源码
# 输入获取 m = int(input()) requirements = list(map(int, input().split())) def check(limit): """ :param limit: 每辆自行车的限重 :return: m辆自行车，每辆限重limit的情况下，能否带走n个人 """ l = 0 # 指向体重最轻的人 r = len(requirements) - 1 # 指向体重最重的人 # 需要的自行车数量 need = 0 while l <= r: # 如果最轻的人和最重的人可以共享一辆车，则l++,r--， # 否则最重的人只能单独坐一辆车，即仅r-- if requirements[l] + requirements[r] <= limit: l += 1 r -= 1 # 用掉一辆车 need += 1 # 如果m >= need，当前有的自行车数量足够 return m >= need def getResult(): requirements.sort() # 每辆自行车的限重 至少是 最重的那个人的体重 low = requirements[-1] # 每辆自行车的限重 至多是 最重的和次重的那两个的体重 high = requirements[-2] + requirements[-1] ans = high # 二分取中间值 while low <= high: mid = (low + high) >> 1 if check(mid): # 如果mid限重，可以满足m辆车带走n个人，则mid就是一个可能解，但不一定是最优解 ans = mid # 继续尝试更小的限重，即缩小右边界 high = mid - 1 else: # 如果mid限重，不能满足m辆车带走n个人，则mid限重小了，我们应该尝试更大的限重，即扩大左边界 low = mid + 1 return ans # 算法调用 print(getResult())C算法源码
#include <stdio.h> #include <stdlib.h> #define MAX_SIZE 10000 /*! * * @param limit 每辆自行车的限重 * @param m m辆自行车 * @param requirements n个人的体重数组 * @param requirements_size n个人 * @return m辆自行车，每辆限重limit的情况下，能否带走n个人 */ int check(long long limit, int m, const int requirements[], int requirements_size) { int l = 0; // 指向体重最轻的人 int r = requirements_size - 1; // 指向体重最重的人 // 需要的自行车数量 int need = 0; while (l <= r) { // 如果最轻的人和最重的人可以共享一辆车，则l++,r--， // 否则最重的人只能单独坐一辆车，即仅r-- if (requirements[l] + requirements[r] <= limit) { l++; } r--; // 用掉一辆车 need++; } // 如果m >= need，当前有的自行车数量足够 return m >= need; } int cmp(const void *a, const void *b) { return *((int *) a) - *((int *) b); } long long getResult(int m, int requirements[], int requirements_size) { qsort(requirements, requirements_size, sizeof(int), cmp); // 每辆自行车的限重 至少是 最重的那个人的体重 long long min = requirements[requirements_size - 1]; // 每辆自行车的限重 至多是 最重的和次重的那两个的体重 long long max = requirements[requirements_size - 2] + requirements[requirements_size - 1]; long long ans = max; // 二分取中间值 while (min <= max) { long long mid = (min + max) >> 1; // 需要注意的是，min，max单独看都不超过int，但是二者相加会超过int，因此需要用long long类型 if (check(mid, m, requirements, requirements_size)) { // 如果mid限重，可以满足m辆车带走n个人，则mid就是一个可能解，但不一定是最优解 ans = mid; // 继续尝试更小的限重，即缩小右边界 max = mid - 1; } else { // 如果mid限重，不能满足m辆车带走n个人，则mid限重小了，我们应该尝试更大的限重，即扩大左边界 min = mid + 1; } } return ans; } int main() { int m; scanf("%d", &m); int requirements[MAX_SIZE]; int requirements_size = 0; while (scanf("%d", &requirements[requirements_size++])) { if (getchar() != ' ') break; } printf("%lld\n", getResult(m, requirements, requirements_size)); return 0; }- 测试用例执行计划（Java JS Python C）)
