首页 > 试题广场 >

分布式计算任务调度

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

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

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

输入描述:
- 第一行:两个整数 NM
- 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 整理上传
头像 Silencer76
发表于 2025-10-11 18:05:58
题目链接 分布式计算任务调度 题目描述 给定 个任务和 个计算节点。每个任务 有一个计算量 。需要将这 个任务分配给 个节点,并遵循以下约束: 顺序性: 分配给节点 的任务 ID 必须全部小于分配给节点 的任务 ID。 连续性: 分配给同一个节点的任务 ID 必须是连续的。 目标是 展开全文