页面加载中…
AI018. 数据分片调度
中等通过率 0% · 提交 0 · 通过 0
华为 AI 岗二分答案贪心划分
算法机考高频题型改编 · 聚焦「华为 AI 岗 / 二分答案」 · 难度：中等
数据管线要把 n 条样本按原顺序切成恰好 k 个连续且非空的分片,每个分片交给一个 worker 串行处理。第 i 条样本的预处理耗时为 t_i,一个 worker 的总耗时是它分片内耗时之和,整条管线的完成时间取决于耗时最大的那个 worker。请输出通过合理切分能达到的最小完成时间。
这类题属于算法机考高频题型中「华为 AI 岗 / 二分答案」方向的高频题型，通常考察对「华为 AI 岗 / 二分答案」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。
输入描述
第一行输入两个整数 n k。第二行输入 n 个整数 t_i。
输出描述
输出一行一个整数,表示最小化的最大分片耗时之和。
示例
示例 1
输入示例
5 2 7 2 5 10 8
输出示例
18
说明：
经典切分
示例 2
输入示例
4 1 5 9 1 7
输出示例
22
说明：
只切一片=总和
时间限制 2000 ms · 内存限制 256 MB
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。
⚠️ 这道题的坑 · 易错点与反直觉
这些是真正决定能不能 AC、但通用题解里常被略过的点。
- 二分下界是 max(t) 不是 0:任何可行上限至少装下最大单条
- 判定条件是最少段数 <= k:段数不够可以继续细分,最大值不会变大
- 段和上限 2×10⁹ 逼近 32 位上限(裕量约 7%),用 64 位保安全
解题思路
这道题在考什么
划分型题面的标准考法:连续切 k 段、最小化最大段和。它有两条路——划分型 DP 和二分答案,这道题的数据范围(n ≤ 2000)故意设计成两条路都能走,但二分答案又快又好写,是机考 200 分档该带上考场的版本。
数据范围读档
O(k·n²) 的划分 DP 最坏 2000³ 量级,会超;它适合先写出来理解题意、在小用例上对拍。正解是对答案二分 + 贪心判定,O(n log(sum)),轻松过全部用例。考场策略:直接写二分;如果二分的判定想不清,DP 版能拿下小数据的部分分。
二分答案:判定函数是灵魂
问题转化成课程第 4 天的判定思维:「上限定为 x 时,能不能切成不超过 k 段?」贪心判定:从左往右装,当前段装不下就开新段,数段数。这个判定关于 x 单调(上限越宽松段数越少),二分成立。
两个边界必须钉死:
- 下界是 max(t) 而不是 0:单条样本不可再切,任何可行上限至少得装下最大的那条。下界写 0 的话,判定函数在 x < max(t) 时会出现「单条都装不下」的未定义行为,要么死循环要么错。
- 判定条件是 最少段数 <= k 而不是 == k:段数少于 k 时可以继续细分,耗时非负,细分不会让最大段和变大。所以「能切成 3 段」蕴含「能切成 5 段」。
主流程
lo, hi = max(t), sum(t)
while lo < hi:
mid = (lo + hi) // 2
if 最少段数(mid) <= k: hi = mid
else: lo = mid + 1答案是 lo。贪心判定里记得先检查单条超上限(有了正确下界后天然不会,但写上更稳)。
易错点展开
- 二分下界写 0。
- 判定写成 == k。
- 段和上限 2000 × 10⁶ = 2×10⁹,虽未超出 32 位上限 2,147,483,647,但裕量只剩约 7%,二分上界与中间量都在这个量级——直接用 64 位保安全裕量。
- k = 1 与 k = n 两个极端(总和 / 最大值)可当自查用例。
参考实现怎么读
参考实现就是主流程那七行二分加一个贪心计数函数。贪心判定里 cur + t > x 时开新段、段数加一;循环结束后段数与 k 比较。整段代码不到三十行,二分答案的题量大多如此——难在想清楚,不在写。
判定函数单调性再啰嗦一句
上限 x 越大,每段能装的越多,最少段数不增——这是二分能用的前提。课程第 4 天珂珂吃香蕉的判定函数是同一个思维:把「求最优值」翻转成「给定值问可不可行」。见到「最小化最大值/最大化最小值」的题面,条件反射应该就是这一手。
写完先自查这三组
1. 样例 1:x = 18 时段数 [7,2,5] [10,8] = 2 段可行,x = 17 时 [7,2,5] [10] [8] = 3 段不可行,答案卡在 18。 2. k = n:每条自成一段,答案 = max(t),验证下界。 3. k = 1:答案 = sum(t),验证上界。
自查用的就是二分的两个端点加一个中间值,三组全对基本收工。
参考代码
# 二分答案:对「最大段和上限 x」二分,贪心判定最少段数是否 <= k
# 下界是 max(t)(单条不可再切),上界是总和;段数可细分所以判定用 <=
import sys
def solve() -> None:
data = sys.stdin.buffer.read().split()
if not data:
return
n = int(data[0])
k = int(data[1])
t = [int(x) for x in data[2:2 + n]]
def feasible(cap: int) -> bool:
seg = 1
cur = 0
for x in t:
if x > cap:
return False
if cur + x > cap:
seg += 1
cur = x
else:
cur += x
return seg <= k
lo = max(t)
hi = sum(t)
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid):
hi = mid
else:
lo = mid + 1
print(lo)
if __name__ == "__main__":
solve()
我的提交
登录后可查看你在本题的历史提交，以及每次的各用例通过情况。
