考点：二分

数据规模 n ≤ 200000 ｜ 限制 2 秒 / 256MB ｜ 标准输入输出

题目画像

• 数据规模：n ≤ 200000，k ≤ 200000
• 元素值域：m ≤ 1e18，c_i ≤ 1e9，w_i ≤ 1e9（注意整数类型选择，避免溢出）
• 复杂度门槛：只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。
• 源站时限：2 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：二分

本题切入点

「最小化瓶颈耗时」二分答案：二分瓶颈值 T，贪心地按顺序尽量多塞层到当前设备（受显存上限 m 约束），判断能否恰好分成 k 段；需先排除单层显存超 m 的无解情况。

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

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

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 ≤ 200000，只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。
• 元素值域最大到 1e18 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 3 4 100 / 1 1 1 / 1 1 1 → 输出 -1

设备数量多于层数，无法保证每段非空。

样例 2：输入 4 2 10 / 2 2 2 2 / 6 6 6 6 → 输出 -1

任意两层的显存之和都超过上限，至少需要四段。

样例 3：输入 5 3 20 / 5 1 2 3 4 / 10 5 5 5 10 → 输出 6

可以依次划分为前两层、中间两层和最后一层，三段计算耗时分别为 6,5,4 。