)
部门人力分配
2025华为OD机试双机位C卷 - 华为OD上机考试双机位C卷 100分题型
华为OD机试双机位C卷真题目录点击查看: 华为OD机试双机位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
输出描述
对于每一组测试数据，输出部门需要人力需求，行末无多余的空格
用例1
输入
3 3 5 3 4输出
6说明
输入数据两行，
第一行输入数据3表示开发时间要求，
第二行输入数据表示需求工作量大小，
输出数据一行，表示部门人力需求。
当选择人力为6时，2个需求量为3的工作可以在1个月里完成，其他2个工作各需要1个月完成。可以在3个月内完成所有需求。当选择人力为5时，4个工作各需要1个月完成，一共需要4个月才能完成所有需求。因此6是部门最小的人力需求。
题解
思路：二分 + 双指针
比较经典的二分题型，一般这种
在满足什么条件下，求最小/最大是比较典型的二分特征题。首先确认上下边界，注意题目限制
1 ≤ N/2 ≤ M其实是已经限制了题目肯定有解。left = 最大要求天数需求，由需要完成的需求不能超过部门人力决定，确定了边界。right = 最大要求天数需求 + 次打要求天数需求由需要完成的需求不能超过部门人力和每个月最多有2个需求开发共同确定。
确定上下边界之后就是枚举找到满足条件的最小部门人数值，每次枚举
mid = (left + right) /2,判断是否可以在m个月完成，然后收缩边界,直到left == right结束:- 不能在m个月完成，移动
left = mid + 1 - 能在m个月满足,移动
right = mid
- 不能在m个月完成，移动
判断是否能在m个月判断采用
双指针进行处理，这里要处理的问题其实在指定人数下，完成这些任务需要的月数，并且一个月最多完成两个任务，为了减少月数，尽量是让每个月完成两个任务。所以采用下面的逻辑，尽量让最小和最大组合，先将requirements升序排序，指针l = 0, r = requirements.size()：- 如果
requirements[l] + requirements[r] <= mid: 进行l++,r --处理,需要处理月份+1 - 否则贪心处理任务量大的,
r--，需要处理月份+1 - 执行1 2逻辑直到
l < r结束，判断需要月份是否小于m
- 如果
二分结束之后，
left 或者right就是结果。
额外注意由于
1≤ requirements[i] ≤ 10^9在计算过程使用int会造成移除，改使用long，对于js推荐使用BigInt处理。
c++
#include<iostream> #include<vector> #include<string> #include <utility> #include <sstream> #include<algorithm> #include<cmath> #include<map> using namespace std; // 通用 切割函数 函数 将字符串str根据delimiter进行切割 vector<int> split(const string& str, const string& delimiter) { vector<int> result; size_t start = 0; size_t end = str.find(delimiter); while (end != string::npos) { result.push_back(stoi(str.substr(start, end - start))); start = end + delimiter.length(); end = str.find(delimiter, start); } // 添加最后一个部分 result.push_back(stoi(str.substr(start))); return result; } bool check(vector<int>& requirements, int personCount, int m) { long needMonth = 0; int l = 0, r = requirements.size() -1; // 双指针求最小月数 while (l <= r) { if (l == r) { needMonth++; r--; continue; } long actualPeronCount = requirements[l] + requirements[r]; // 一同处理 if (actualPeronCount <= personCount) { l++; r--; // 选择消耗工作量大的 } else { r--; } needMonth++; } return needMonth <= m; } int main() { int m; cin >> m; string input; // 忽略空行 cin.ignore(); getline(cin, input); vector<int> requirements = split(input, " "); int n = requirements.size(); sort(requirements.begin(), requirements.end()); // 每个月需要完成的需求不能超过部门人力，决定必须满足单个需求可以在一个月完成 long left = requirements[n-1]; // 单月最多两个需求，限制了最大人数 long right = requirements[n-1] + requirements[n - 2]; // 二分 while (left < right) { long mid = (left + right) >> 1; if (check(requirements, mid, m)) { right = mid; } else { left = mid + 1; } } cout << left; return 0; }JAVA
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { // 判断在 personCount 人力下，是否能在 m 个月内完成 static boolean check(List<Integer> requirements, long personCount, int m) { long needMonth = 0; int l = 0, r = requirements.size() - 1; // 双指针求最小月数 while (l <= r) { if (l == r) { needMonth++; r--; continue; } long actualPersonCount = requirements.get(l) + requirements.get(r); // 一同处理 if (actualPersonCount <= personCount) { l++; r--; } else { // 只能处理大的那个 r--; } needMonth++; } return needMonth <= m; } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int m = Integer.parseInt(br.readLine()); String[] parts = br.readLine().trim().split("\\s+"); List<Integer> requirements = new ArrayList<>(); for (String p : parts) { requirements.add(Integer.parseInt(p)); } Collections.sort(requirements); int n = requirements.size(); // 单个需求必须能在一个月完成 long left = requirements.get(n - 1); // 单月最多两个需求 long right = requirements.get(n - 1) + requirements.get(n - 2); // 二分查找 while (left < right) { long mid = (left + right) >> 1; if (check(requirements, mid, m)) { right = mid; } else { left = mid + 1; } } System.out.println(left); } }Python
defcheck(requirements,person_count,m):need_month=0l,r=0,len(requirements)-1# 双指针求最小月数whilel<=r:ifl==r:need_month+=1r-=1continueactual_person_count=requirements[l]+requirements[r]# 一同处理ifactual_person_count<=person_count:l+=1r-=1else:# 只能处理大的那个r-=1need_month+=1returnneed_month<=m m=int(input())requirements=list(map(int,input().split()))requirements.sort()n=len(requirements)# 单个需求必须能在一个月完成left=requirements[-1]# 单月最多两个需求right=requirements[-1]+requirements[-2]# 二分查找whileleft<right:mid=(left+right)//2ifcheck(requirements,mid,m):right=midelse:left=mid+1print(left)JavaScript
constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});letlines=[];rl.on('line',line=>{lines.push(line.trim());});rl.on('close',()=>{constm=BigInt(lines[0]);constrequirements=lines[1].split(/\s+/).map(BigInt);requirements.sort((a,b)=>(a<b?-1:1));functioncheck(personCount){letneedMonth=0n;letl=0,r=requirements.length-1;while(l<=r){if(l===r){needMonth++;r--;continue;}constactualPersonCount=requirements[l]+requirements[r];if(actualPersonCount<=personCount){l++;r--;}else{r--;}needMonth++;}returnneedMonth<=m;}letleft=requirements[requirements.length-1];letright=requirements[requirements.length-1]+requirements[requirements.length-2];// BigInt 二分while(left<right){constmid=(left+right)/2n;if(check(mid)){right=mid;}else{left=mid+1n;}}console.log(left.toString());});Go
packagemainimport("bufio""fmt""os""sort")funccheck(requirements[]int,personCountint64,mint)bool{varneedMonthint64=0l,r:=0,len(requirements)-1// 双指针求最小月数forl<=r{ifl==r{needMonth++r--continue}actualPersonCount:=int64(requirements[l]+requirements[r])// 一同处理ifactualPersonCount<=personCount{l++r--}else{// 只能处理大的那个r--}needMonth++}returnneedMonth<=int64(m)}funcmain(){in:=bufio.NewReader(os.Stdin)varmintfmt.Fscanln(in,&m)varrequirements[]intfor{varxint_,err:=fmt.Fscan(in,&x)iferr!=nil{break}requirements=append(requirements,x)}sort.Ints(requirements)n:=len(requirements)// 单个需求必须能在一个月完成left:=int64(requirements[n-1])// 单月最多两个需求right:=int64(requirements[n-1]+requirements[n-2])// 二分查找forleft<right{mid:=(left+right)>>1ifcheck(requirements,mid,m){right=mid}else{left=mid+1}}fmt.Println(left)}
