华为 · 二分 · 算法编程题
华为 二分 N ≤ 1e3 时限 1 秒 / 256 MB

题目描述

一个分布式计算系统中有 M 个处理节点，所有节点的初始负载均为零。
现在有 N 个计算任务需要处理，这些任务按其依赖关系顺序编号，ID 从 0 到 N-1 。
你需要设计一个任务分配方案，使得各计算节点间的负载差异最小化。
说明：
- 任务分配完成后，负载最高的节点的负载量记为 X 。
- 负载最低的节点的负载量记为 Y 。
- 你的目标是找到一种分配方案，使得 X - Y 的值最小。
任务的分配必须满足以下严格的约束条件：
1. 顺序性：对于任意节点编号 i < j ，分配给节点 i 的所有任务的 ID 必须小于分配给节点 j 的所有任务的 ID。
2. 连续性：分配给同一个节点的一组任务，它们的 ID 必须是连续的。
3. 原子性：单个任务不可拆分，必须完整地分配给一个节点。

输入输出

输入描述
- 第一行：两个整数 N 和 M 。
- N 是任务的总数，其范围为 1 ≤ N ≤ 1000 。
- M 是计算节点的数量，其范围为 1 ≤ M ≤ N 。
- 第二行： N 个整数 C_0, C_1, ..., C_N-1 ，其中 C_i 代表 ID 为 i 的任务所需的计算量。计算量的范围为 1 ≤ C_i ≤ 100000 。
输出描述
输出在最优分配方案下，负载最高的节点的负载量 X 。

样例共 1 组

样例 1
输入
6 5
32 44 98 73 46 98
输出
98

算法解析依据充分

考点：二分

数据规模 N ≤ 1e3 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：N ≤ 1e3
  • 元素值域：C_i ≤ 1e5（注意整数类型选择，避免溢出）
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：二分

本题切入点

二分「负载极差上限 D」，再用 DP/贪心判断能否把任务切成 M 段连续子数组、使每段和都落在 [lo, lo+D] 内；可行则收紧 D，最终输出最优方案下的最高负载 X。

把「求最优值」转化为「判定某值是否可行」，用单调性二分逼近答案。

思路框架（二分 通法 · 非本题专属）

  1. 确认单调性：答案越大/越小，条件越容易（或越难）满足。
  2. 写出 check(x)：判断值为 x 时是否可行。
  3. 在答案区间 [lo, hi] 上二分，每次取 mid 调 check，收缩区间。
  4. 边界收敛到唯一答案，注意取整方向（求最小可行值用上取整）。

实现要点：模板：while (lo < hi) { mid = (lo+hi)/2; if (check(mid)) hi = mid; else lo = mid+1; } 求最小可行值。

复杂度：时间 O(check 的代价 × log(答案范围)) ｜ 空间 O(1)

该范式的通法易错点

  • check 函数不满足单调性却硬套二分（会得到错误答案）。
  • 二分边界或取整方向写错，陷入死循环或漏掉边界答案。

对照本题

  • 数据规模 N ≤ 1e3，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 元素值域最大到 1e5 —— 求和 / 相乘时记得开 64 位整数。

样例

样例 1

  • 输入：6 5 / 32 44 98 73 46 98
  • 输出：98

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2025年秋招-华为-10月10号开发岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解