CodeForces 545C Woodcutters：貪心策略最大化砍伐樹木數量

題目大意

有 n 棵樹，第 i 棵位於座標 x[i]，高度 h[i]。樹可向左倒（佔用 [x[i]-h[i], x[i]]）或向右倒（佔用 [x[i], x[i]+h[i]]），或不砍。樹倒下區間不能重疊。求最多能砍幾棵樹。

貪心策略

• 第一棵樹總是向左倒（左側無樹），最後一棵總是向右倒（右側無樹）。
• 中間樹按順序處理：優先嘗試向左倒（x[i] - h[i] > last），若不可則嘗試向右倒（x[i] + h[i] < x[i+1]），否則不砍。
• last 記錄已佔用區間的最右端點，初始為 -inf。

C++ 實現

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<long long> x(n), h(n);
    for (int i = 0; i < n; ++i) cin >> x[i] >> h[i];
    if (n <= 2) { cout << n << '\n'; return 0; }

    int ans = 2;  // 首尾必砍
    long long last = x[0];  // 第一棵向左倒，佔用到 x[0]
    for (int i = 1; i + 1 < n; ++i) {
        if (x[i] - h[i] > last) {  // 向左
            ++ans;
            last = x[i];
        } else if (x[i] + h[i] < x[i+1]) {  // 向右
            ++ans;
            last = x[i] + h[i];
        } else {
            last = x[i];  // 不砍，佔用點 x[i]
        }
    }
    cout << ans << '\n';
    return 0;
}

正確性直覺

向左倒不影響後續樹的決策空間（只佔用左側），向右倒會壓縮後續空間。故優先向左是局部最優，並能推導出全域最優。

複雜度

• 時間：O(n) 單次遍歷。
• 空間：O(n) 存儲輸入。