页面加载中…
P3307. 部门人力分配
中等通过率 46% · 提交 1,256 · 通过 576
200分双指针2024E贪心二分查找双机位C排序
华为 OD 机考真题方向改编 · 聚焦「200分 / 双指针」 · 难度：中等
小慕在负责一个项目的需求开发，需要合理安排人力。当前项目共有 N 个需求，每个需求的工作量用 requirements[i] 表示，单位是。这些需求需要在 M 个月内完成开发，且每个月安排的人力是固定的。 每个月最多只能同时开发 2 个需求，并且当月所有需求的工作量总和不能超过当月的人力。请帮小慕计算，在满足项目进度要求的前提下，是多少。
这类题属于华为 OD 机考真题方向中「200分 / 双指针」方向的高频题型，通常考察对「200分 / 双指针」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。
提示：带虚线的词点一下有通俗解释。
输入描述
输入第一行为 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是部门最小的人力需求。
时间限制 1000 ms · 内存限制 128 MB
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。
相关图解步骤
把本题套路迁移到 LeetCode 动画里看
先看指定步骤补关键知识点，再回到本题完成标准输入输出。
解题思路
题目描述不是特别清晰，只能通过示例进行反推。
子问题定义
考虑子问题，在设置人力需求为 k 时，需要多少个月能够完成所有工作。这个子问题与课上讲过的 经典题型. 救生艇 是完全一致的。
子问题中的人力需求 k 就等价于救生艇中的最大承重 limit，且每次选择都只能至多选择数组中的两个元素。该子问题使用 排序 + 双指针 + 贪心 的策略来完成，其代码如下：
注意 nums 数组必须先排序，才可以使用上述的贪心策略。
二分查找确定 k
再得到 check 函数之后，就需要找到一个适合的 k 了。显然 k 的取值是存在二段性的：
- 当
k很小时，需要 N 个月才能完成工作，即每一个月都只能完成 1 个工作 - 当
k很大时，可以只花 N/2 个月就完成工作，即每一个月都可以完成 2 个工作
又因为 N/2 ≤ M ≤ N 成立，故一定存在一个 k，恰好能够在 M 个月内完成工作。
因此考虑二分查找完成本题。其主要代码如下：
PS：本题综合性比较强，同时涉及了双指针、贪心和二分查找，还需要大家多加练习以将所有知识融会贯通。
复杂度分析 设 n 为需求个数（数组 nums 的长度），S 为所有需求工作量之和 sum(nums)。
- 预处理排序 nums.sort() 为 O(n log n)，只做一次，它是后续双指针贪心配对正确性的前提。
- check 函数用首尾双指针配对：每一轮 while 循环至少让 right 左移一次，两指针相遇即结束，单次调用为 O(n)。
- 二分在区间 [max(nums), sum(nums)+1) 上进行，迭代次数为 O(log S)，每轮调用一次 check。
因此总时间复杂度为 O(n log n + n log S)，主导项是二分乘线性检查的 n log S。空间上排序原地进行，check 只用 left、right、ans 三个变量，除输入数组外额外空间复杂度为 O(1)。
我的提交
登录后可查看你在本题的历史提交，以及每次的各用例通过情况。
