题目理解

我们有 N 棵灌木，每棵初始高度 hᵢ，每天生长 dᵢ。

每天：

1. 所有树先生长（加上 dᵢ）
2. 然后园丁进行最多 k 次修剪，每次修剪可以从一棵树剪掉恰好 x 厘米（如果树高 ≥ x）

M 天后，我们希望最高的树的高度尽可能小。

---

关键点

• 修剪是离散的：每次只能剪 x 厘米
• 每天最多 k 次修剪
• 目标是 minimize(最高高度)

---

思路

这是一个最小化最大值的问题，通常可以用二分答案解决。

设我们猜测最终最高高度为 H，检查是否可能通过修剪使得 M 天后所有树高度 ≤ H。

---

检查函数

对于每棵树 i：

• 初始高度 hᵢ
• 每天生长 dᵢ
• 经过 M 天，如果不修剪，最终高度 = hᵢ + M × dᵢ
• 如果这个值 ≤ H，则不需要修剪
• 否则，需要修剪掉多余的部分：extra = hᵢ + M × dᵢ - H

但修剪是离散的（每次剪 x），并且每天最多 k 次。

---

修剪策略

我们可以在任意一天修剪任意树，只要树高 ≥ x。

为了最小化最高高度，我们应该尽早修剪，因为越早修剪，后续生长越少。

对于一棵需要修剪 extra 厘米的树，由于每次剪 x，需要修剪次数 = ceil(extra / x)。

但修剪次数有限制：总共 M 天，每天最多 k 次，所以总修剪次数 ≤ M × k。

---

检查可行性

对于猜测的 H，计算每棵树 i 需要的修剪次数： needᵢ = max(0, ceil( (hᵢ + M × dᵢ - H) / x ))

如果 Σ needᵢ ≤ M × k，则可行。

但这样计算不对，因为修剪可以分散到多天，并且修剪会影响后续生长。

---

正确计算修剪次数

设第 i 棵树在第 t 天被修剪 cᵢ,ₜ 次（0 ≤ cᵢ,ₜ ≤ 每天最多？不对，每天总共最多 k 次，不是每棵树）。

修剪后的高度会影响后续生长。

更精确地：如果树 i 在第 t 天被修剪 cᵢ,ₜ 次，那么那天它被剪掉 cᵢ,ₜ × x 厘米。

最终高度 = 初始高度 + 总生长 - 总修剪量 = hᵢ + M × dᵢ - x × Σₜ cᵢ,ₜ

我们需要最终高度 ≤ H，所以： Σₜ cᵢ,ₜ ≥ ceil( (hᵢ + M × dᵢ - H) / x )

并且每天所有树的修剪次数总和 ≤ k。

---

问题转化

我们需要判断是否存在 cᵢ,ₜ 满足：

1. 对每棵树 i：Σₜ cᵢ,ₜ ≥ needᵢ
2. 对每天 t：Σᵢ cᵢ,ₜ ≤ k
3. cᵢ,ₜ 是非负整数

其中 needᵢ = ceil( (hᵢ + M × dᵢ - H) / x )

这是一个分配问题：有 M 天（每天容量 k），N 棵树（每棵需要 needᵢ 次修剪），是否可行？

显然可行的条件是： Σ needᵢ ≤ M × k

因为我们可以把修剪均匀分配到每天。

---

检查函数

对于猜测的 H： need_total = Σ max(0, ceil( (hᵢ + M × dᵢ - H) / x )) 如果 need_total ≤ M × k，则可行。

---

二分答案范围

下界：0（可能所有树修剪到 0） 上界：max(hᵢ + M × dᵢ)（不修剪时的最大高度）

---

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

int main() {
    int N, M, k, x;
    cin >> N >> M >> k >> x;
    
    vector<ll> h(N), d(N);
    ll max_possible = 0;
    for (int i = 0; i < N; i++) {
        cin >> h[i] >> d[i];
        max_possible = max(max_possible, h[i] + M * d[i]);
    }
    
    ll left = 0, right = max_possible;
    ll ans = max_possible;
    
    while (left <= right) {
        ll mid = (left + right) / 2;
        
        // 计算总修剪次数
        ll total_cuts = 0;
        for (int i = 0; i < N; i++) {
            ll final_height = h[i] + M * d[i];
            if (final_height > mid) {
                ll need = (final_height - mid + x - 1) / x;
                total_cuts += need;
            }
        }
        
        if (total_cuts <= (ll)M * k) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

---

样例验证

输入：

4 3 4 3
2 5
3 2
0 4
2 8

输出：8 ✅

---

复杂度

• 二分答案：O(log(max_height))
• 每次检查：O(N)
• 总复杂度：O(N log(max_height))，可以处理 N ≤ 10⁴

这个解法通过二分猜测最终高度，用数学计算需要的修剪次数，判断是否在总修剪次数限制内，从而找到最小的最大高度。