考点：二分

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

题目画像

• 数据规模：n ≤ 1e5
• 元素值域：B ≤ 100000000000，C ≤ 100，F ≤ 100（注意整数类型选择，避免溢出）
• 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
• 源站时限：2 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：二分

本题切入点

二分最终最低高度 H：判断预算是否够把每个低于 H 的花圃补到 H（土量×U + 所需车数×F ≤ B），该判定关于 H 单调，故可二分。

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

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

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²) 会超时。
• 元素值域最大到 100000000000 —— 求和 / 相乘时记得开 64 位整数。

样例解读

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

抬高到 11 需要 40 单位土，填埋费 80、运输费 20。

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

抬高到 4 总成本 35，抬高到 5 总成本 53。