(100分)- 部门人力分配（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

输出描述

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

用例

题目解析

本题是将二分和双指针考点结合在了一起。

本题我们可以换个说法：

目前有 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; }