首页 > 试题广场 >

分布式计算任务调度

[编程题]分布式计算任务调度
  • 热度指数：112 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
一个分布式计算系统中有 M 个处理节点，所有节点的初始负载均为零。
现在有 N 个计算任务需要处理，这些任务按其依赖关系顺序编号，ID 从 0 到 N-1。
你需要设计一个任务分配方案，使得各计算节点间的负载差异最小化。

说明：
- 任务分配完成后，负载最高的节点的负载量记为 X。
- 负载最低的节点的负载量记为 Y。
- 你的目标是找到一种分配方案，使得 X - Y 的值最小。

任务的分配必须满足以下严格的约束条件：
1. 顺序性：对于任意节点编号 i < j，分配给节点 i 的所有任务的 ID 必须小于分配给节点 j 的所有任务的 ID。
2. 连续性：分配给同一个节点的一组任务，它们的 ID 必须是连续的。
3. 原子性：单个任务不可拆分，必须完整地分配给一个节点。

输入描述:
- 第一行：两个整数 N 和 M。
- N 是任务的总数，其范围为 1 \le N \le 1000。
- M 是计算节点的数量，其范围为 1 \le M \le N。
- 第二行：N 个整数 C_0, C_1, \dots, C_{N-1}，其中 C_i 代表 ID 为 i 的任务所需的计算量。计算量的范围为 1 \le C_i \le 100000。


输出描述:
输出在最优分配方案下，负载最高的节点的负载量 X。
示例1

输入

6 5
32 44 98 73 46 98

输出

98

备注:
本题由牛友@Charles 整理上传
算法知识视频讲解
添加回答
StLeoX头像 StLeoX
居然是贪心+二分，我用回溯+记忆化超时了。
发表于 2025-10-12 15:07:53 回复(0)
Sen🍓🍀头像 Sen🍓🍀
n个任务划分为m个连续段, 记m个段和最大值max, 最小值min, 要求max-min最小
因为总和一定, max越小, min越大, 差距max-min就越小  (?)
最大值最小：二分猜答案 + check()
发表于 2025-10-12 12:13:36 回复(0)
提交观点

问题信息

来自：2025年秋招-华为-...
难度：
2条回答 12浏览

热门推荐

相关试题

分布式计算任务调度

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号