ZeroJudge 解題筆記：r783.Tree cutting

作者：王一哲
日期：2026年11月6日


ZeroJudge 題目連結：r783.Tree cutting

解題想法

每組測資第一列為兩個整數 $n ~(1 \leq n \leq 10^6), m ~(1 \leq m \leq 2 \times 10^9)，分別代表有 $n$ 棵樹，需要長度 $m$ 的木材。第二列有 $n$ 個整數，代表這 $n$ 棵樹各自的高度。這個人使用的電鋸比較特別，先調整好鋸片離地的高度之後，一次砍下整排樹高於鋸片的部分。如果要取得總長度大於、等於 $m$ 的木材，鋸片離地高度最大值為何？

這題要對答案二分搜，先設定答案下限 $low = 0$，上限 $high$ 為樹的最大高度，答案 $ans = 0$。我習慣用閉區間寫對答案二分搜，while 迴圈的條件是 $low \leq high$，每次執行時先計算中點 $mid = (high - low) / 2 + low$，再計算高度大於 $mid$ 的樹高度減去 $mid$ 的加總 $isum$，如果 $isum \geq m$，設定答案 $ans = min(ans, mid)$，提高答案下限 $low = mid + 1$；反之，降低答案上限 $high = mid - 1$。

不過這題的 $n$ 很大，如果在 while 迴圈當中再用一個 for 迴圈計算 $isum$ 會超時。所以要先將樹的高度 $hs$ 加上一個 0，由小到大排序，這樣就可以用內建的二分搜工具，例如 Python bisect_left 或是 C++ lower_bound，從 $hs$ 之中快速地找到第一個大於、等於 $mid$ 的索引值。為了快速地計算 $hs[idx]$ 到最後一項的高度加總，還要再開一個陣列 $psum$ 計算 $hs$ 的前綴和。加上這個部分之後就能夠 AC。不過我的寫法應該還可以再加速。

Python 程式碼

使用時間約為 1 s，記憶體約為 170.3 MB，通過測試。

def solve():
    import sys
    from bisect import bisect_left

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])  # n 棵樹
        m = int(data[ptr + 1])  # 需要總長度 m 的木材
        ptr += 2
        hs = [0] + sorted(map(int, data[ptr : ptr + n]))  # n 棵樹的高度，由小到大排序，開頭加一個 0
        ptr += n
        psum = hs[:]  # 前綴和
        for i in range(1, n + 1):
            psum[i] += psum[i - 1]

        # 對答案二分搜
        low, high, ans = 0, max(hs), 0
        while low <= high:
            mid = (low + high) // 2
            # 用 bisect_left 找出 hs 之中第一個大於、等於 mid 的索引值
            idx = bisect_left(hs, mid)
            # 如果有找到，用 psum 計算 hs[idx:] 區間和 - mid * 區間長度
            isum = 0
            if idx <= n:
                isum = psum[n] - psum[idx - 1] - mid * (n - idx + 1)
            if isum >= m:  # 超過所需要的量，試著提高下限
                ans = max(ans, mid)
                low = mid + 1
            else:  # 不足，試著降低上限
                high = mid - 1
        result.append(f"{ans:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

使用時間約為 0.2 s，記憶體約為 18.5 MB，通過測試。

#include <iostream>
#include <vector>
#include <algorithm>
typedef long long LL;
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;  // n 棵樹
    LL m;  // 需要總長度 m 的木材
    while(cin >> n >> m) {
        // n 棵樹的高度，由小到大排序，開頭加一個 0
        vector<LL> hs (n + 1, 0);
        LL high = 0;  // 最大高度
        for(int i = 1; i <= n; i++) {
            LL h;
            cin >> h;
            hs[i] = h;
            high = max(high, h);
        }
        sort(hs.begin(), hs.end());
        
        // 樹高的前綴和
        vector<LL> psum (hs.begin(), hs.end());
        for(int i = 1; i <= n; i++) {
            psum[i] += psum[i - 1];
        }

        // 對答案二分搜
        LL low = 0, ans = 0;
        while(low <= high) {
            LL mid = (high - low) / 2 + low;
            // 用 lower_bound 找出 hs 之中第一個大於、等於 mid 的索引值
            int idx = lower_bound(hs.begin(), hs.end(), mid) - hs.begin();
            // 如果有找到，用 psum 計算 hs[idx:] 區間和 - mid * 區間長度
            LL isum = 0;
            if (idx <= n) {
                isum = psum[n] - psum[idx - 1] - mid * (n - idx + 1);
            }

            if (isum >= m) {  // 超過所需要的量，試著提高下限
                ans = max(ans, mid);
                low = mid + 1;
            } else {  // 不足，試著降低上限
                high = mid - 1;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}