考点：二分

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

题目画像

• 数据规模：n ≤ 1e5
• 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
• 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：二分

本题切入点

答案（施法次数）具有单调性，二分答案后用 check 判定「给定次数能否打完全部气球」。

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

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

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 ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。

样例解读

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

第一次释放选择对第三个气球多承受1点伤害，三个气球的坚韧度变成：0 2 2 。第二次释放后所有气球的坚韧度都为0。