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

题目描述

部门在进行需求开发时需要进行人力安排。

当前部门需要完成 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就是一个