最新华为OD机试真题-部门项目任务分配(100分)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解
👏 感谢大家的订阅➕ 和 喜欢💗
📎在线评测链接
🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁~
🍓OJ题目截图
🍌 部门项目任务分配
问题描述
卢小姐所在的部门正在进行项目开发,需要在 个月内完成
个任务。每个任务的工作量用
表示,单位为人月。为了提高效率,部门要求每个月最多同时进行
个任务,且每个月完成的任务总工作量不能超过该月的人力资源数。请帮助卢小姐确定在满足任务开发进度要求的情况下,每个月所需的最小人力资源数。
输入格式
第一行包含一个整数 ,表示项目开发时间。
第二行包含 个空格分隔的整数
,表示每个任务的工作量。
输出格式
输出一个整数,表示每个月所需的最小人力资源数。
样例输入
3
3 5 3 4
样例输出
6
数据范围
题解
本题可以使用二分答案的思路来解决。可以将每个月的人力资源数二分枚举,判断当前枚举的人力资源数是否满足任务开发的要求。
具体步骤如下:
-
将任务工作量数组
按照从小到大排序。
-
二分枚举人力资源数的范围,左端点为
中的最大值,右端点为
。
-
对于每个枚举的人力资源数
,使用双指针判断是否满足任务开发要求:
- 初始化左右指针
和
分别指向
的左右端点。
- 如果
,表示当前两个任务可以在同一个月完成,将左指针右移,右指针左移。
- 否则,只能完成右指针指向的任务,将右指针左移。
- 每次指针移动,计数器
加
,表示需要的月数。
- 如果
,说明当前枚举的人力资源数满足要求,缩小右端点;否则,增大左端点。
- 初始化左右指针
-
二分结束后,左端点即为所需的最小人力资源数。
时间复杂度为 ,空间复杂度为
。
参考代码
- Python
def check(x):
cnt = 0
l, r = 0, n - 1
while l <= r:
if tasks[l] + tasks[r] <= x:
l += 1
r -= 1
else:
r -= 1
cnt += 1
return cnt <= m
m = int(input())
tasks = list(map(int, input().split()))
n = len(tasks)
tasks.sort()
left, right = tasks[-1], 10**9
while left < right:
mid = left + right >> 1
if check(mid):
right = mid
else:
left = mid + 1
print(left)
- Java
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static final int N = 10005;
static int n, m;
static int[] tasks = new int[N];
public static boolean check(int x) {
int cnt = 0;
int l = 0, r = n - 1;
while (l <= r) {
if (tasks[l] + tasks[r] <= x) {
l++;
r--;
} else {
r--;
}
cnt++;
}
return cnt <= m;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
m = scanner.nextInt();
while (scanner.hasNext()) {
tasks[n++] = scanner.nextInt();
}
Arrays.sort(tasks, 0, n);
int left = tasks[n - 1], right = (int) 1e9;
while (left < right) {
int mid = left + (right - left) / 2;
if (check(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
System.out.println(left);
}
}
- Cpp
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e4 + 5;
int n, m;
int tasks[N];
bool check(int x) {
int cnt = 0;
int l = 0, r = n - 1;
while (l <= r) {
if (tasks[l] + tasks[r] <= x) {
l++;
r--;
} else {
r--;
}
cnt++;
}
return cnt <= m;
}
int main() {
cin >> m;
while (cin >> tasks[n]) n++;
sort(tasks, tasks + n);
int left = tasks[n - 1], right = 1e9;
while (left < right) {
int mid = left + right >> 1;
if (check(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
cout << left << endl;
return 0;
}
#华为od##华为##华为od题库##华为OD机试算法题库#最新华为OD机试-D卷 文章被收录于专栏
本专栏给大家提供了华为2024最新华为OD-C/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 提供OJ在线评测