# APCS實作題2020年1月第3題：砍樹

> 日期：2024年7月10日
> 作者：王一哲
> 題目來源：2020年1月實作題第3題
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=h028)

## 題目

### 問題描述

有一個長度為 $L$ 的長條型的林場，$N$ 棵樹種在一排，現階段砍樹必須符合以下的條件：「讓它向左或向右倒下，倒下時不會超過林場的左右範圍之外，也不會壓到其它尚未砍除的樹木。」你的工作就是計算能砍除的樹木。

若 $c_i$ 代表第 $i$ 棵樹的位置座標，$h_i$ 代表高度。向左倒下壓到的範圍為 $[c_i - h_i, c_i]$，而向右倒下壓到的範圍為 $[c_i, c_i + h_i]$。如果倒下的範圍內有其它尚未砍除的樹就稱為壓到，剛好在端點不算壓到。

我們可以不斷找到滿足砍除條件的樹木，將它砍倒後移除，然後再去找下一棵可以砍除的樹木，直到沒有樹木可以砍為止。無論砍樹的順序為何，最後能砍除的樹木是相同的。
<br />

### 輸入說明

第一行為正整數 $N$ 以及一個正整數 $L$，代表樹的數量與林場右邊界的座標。$N \leq 10^5$，$L \leq 10^9$。

第二行有 $N$ 個正整數依序代表這 $N$ 棵樹的座標，座標是從小到大排序的，所有座標不超過 $L$。

第三行有 $N$ 個正整數依序代表樹的高度，所有樹高都不超過 $10^9$。

本題包含三個子題組，每個子題組配分如下：
1. 第1子題組共20分：$N \leq 10$
2. 第2子題組共40分：$N \leq 1000$
3. 第3子題組共40分：無額外限制。

<br />

### 輸出格式

輸出共有兩行，第一行輸出能被砍除之樹木數量，第二行輸出能被砍除之樹木中最高的高度，如果無法砍除任何一棵樹，則最高高度輸出 0。
<br />

### 範例輸入1

6 140
10 30 50 70 100 125
30 15 55 10 55 25

### 範例輸出1

4
30

### 範例輸入2

1 10
5
6

### 範例輸出2

0
0

<br />

## Python 程式碼

### 寫法1，使用 pop 移除資料

程式邏輯無誤，但是效率不好，主要問題在於第16、17行的 pop，第12筆測資超時。

N, L = map(int, input().split())  # 讀數數量N、長度L
ps = list(map(int, input().split()))  # 讀取樹的位置
hs = list(map(int, input().split()))  # 讀取樹的高度
ps = [0] + ps + [L]  # 在位置兩端分別加上0及L，避免在迴圈檢查時出界
hs = [0] + hs + [0]  # 在位置兩端加上0，避免在迴圈檢查時出界
flag = True  # 是否有砍樹
imax = 0  # 最大高度
count = 0  # 砍樹數量

while flag:  # 如果有砍樹，繼續執行
    flag = False  # flag 重設為 False
    i = 1  # 檢查樹的索引值從1開始
    while i < len(ps)-1:  # 如果i小於 ps 長度減1
        if ps[i] - ps[i-1] >= hs[i] or ps[i+1] - ps[i] >= hs[i]:  # 如果不會壓到左側或右側的樹
            flag = True  # 有砍樹
            ps.pop(i)  # 移除這棵樹的位置 ps[i]
            imax = max(imax, hs.pop(i))  # 更新 imax 並移除 hs[i]
            count += 1  # 數量加1
            continue  # 繼續執行下一輪內層的 while 迴圈
        i += 1  # 如果上面的 if 不成立，i加1，檢查下一棵樹
""" end while loop """
print(count)  # 印出數量
print(imax)  # 印出最大高度

<br /><br />

### 寫法2，記錄左側、右側樹的索引值，不移除資料

費時最久約為 0.4 s，使用記憶體最多約為 35 MB，通過測試。

N, L = map(int, input().split())  # 讀數數量N、長度L
ps = list(map(int, input().split()))  # 讀取樹的位置
hs = list(map(int, input().split()))  # 讀取樹的高度
ps = [0] + ps + [L]  # 在位置兩端分別加上0及L，避免在迴圈檢查時出界
hs = [0] + hs + [0]  # 在位置兩端加上0，避免在迴圈檢查時出界
left = list(range(-1, N+1))  # 第i棵樹對應的左側樹索引值
right = list(range(1, N+3))  # 第i棵樹對應的右側樹索引值
imax = 0  # 最大高度
count = 0  # 砍樹數量
i = 1  # 檢查樹的索引值從1開始

""" 主要的解題過程 """
while True:
    if ps[i] - ps[left[i]] >= hs[i] or ps[right[i]] - ps[i] >= hs[i]:  # 如果不會壓到左側或右側的樹
        imax = max(imax, hs[i])  # 更新 imax
        count += 1  # 數量加1
        left[right[i]] = left[i]  # 取出第i棵樹右側索引值 right[i]，將它對應的左側索引值更新為 left[i]
        right[left[i]] = right[i]  # 取出第i棵樹右側索引值 left[i]，將它對應的右側索引值更新為 right[i]
        if left[i] != 0: i = left[i]  # 如果有左側的樹，i 更新為 left[i]
        else: i = right[i]  # 如果沒有左側的樹，i 更新為 right[i]
    else: i = right[i]  # 如果沒有砍樹，找右側下一棵樹，i 更新為 right[i]
    if i > N: break  # 如果 i > N，出界，中止 while 迴圈
""" end while loop """

print(count)  # 印出數量
print(imax)  # 印出最大高度

<br /><br />

## C++ 程式碼

### 寫法1，使用 erase 移除資料

程式邏輯無誤，但是效率不好，主要問題在於第23、24行的 erase，第12筆測資超時。

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N, L; cin >> N >> L;  // 讀數數量N、長度L
    vector<int> ps (N+2, 0), hs (N+2, 0);  // 樹的位置 ps、高度 hs
    ps[N+1] = L;  // 在位置右端加上L，避免在迴圈檢查時出界
    for(int i=1; i<=N; i++) cin >> ps[i];  // 讀取 ps
    for(int i=1; i<=N; i++) cin >> hs[i];  // 讀取 hs
    bool flag = true;  // 是否有砍樹
    int imax = 0, count = 0;  // 最大高度 imax，砍樹數量 count
    
    while(flag) {  // 如果有砍樹，繼續執行
        flag = false;  // flag 重設為 False
        int i = 1;  // 檢查樹的索引值從1開始
        while(i < (int)ps.size()-1) {  // 如果i小於 ps 長度減1
            if (ps[i] - ps[i-1] >= hs[i] || ps[i+1] - ps[i] >= hs[i]) {  // 如果不會壓到左側或右側的樹
                flag = true;  // 有砍樹
                imax = max(imax, hs[i]);  // 更新 imax
                count++;  // 數量加1
                ps.erase(ps.begin()+i);  // 移除 ps[i]
                hs.erase(hs.begin()+i);  // 移除 hs[i]
                continue;  // 繼續執行下一輪內層的 while 迴圈
            }
            i++;  // 如果上面的 if 不成立，i加1，檢查下一棵樹
        }
    }
    
    cout << count << "\n" << imax << "\n";  // 印出答案
    return 0;
}

<br /><br />

### 寫法2，記錄左側、右側樹的索引值，不移除資料

費時最久約為 32 s，使用記憶體最多約為 1.9 MB，通過測試。

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N, L; cin >> N >> L;  // 讀數數量N、長度L
    vector<int> ps (N+2, 0), hs (N+2, 0), left (N+2, 0), right (N+2, 0);  // 樹的位置 ps、高度 hs、左側樹 left、右側樹 right
    ps[N+1] = L;  // 在位置右端加上L，避免在迴圈檢查時出界
    for(int i=1; i<=N; i++) cin >> ps[i];  // 讀取 ps
    for(int i=1; i<=N; i++) cin >> hs[i];  // 讀取 hs
    for(int i=1; i<=N+1; i++) {
        left[i] = i-1;   // 0, 1, 2, ..., N
        right[i] = i+1;  // 1, 2, 3, ..., N+2
    }
    int imax = 0, count = 0, i = 1;  // 最大高度 imax，砍樹數量 count，正在檢查的樹索引值 i 從 1 開始
    /* 主要的解題過程 */
    while(true) {
        if (ps[i] - ps[left[i]] >= hs[i] || ps[right[i]] - ps[i] >= hs[i]) {  // 如果不會壓到左側或右側的樹
            imax = max(imax, hs[i]);  // 更新 imax
            count++;  // 數量加1
            right[left[i]] = right[i];  // 取出 left[i]，將它對應的右側樹位置設定為 right[i]
            left[right[i]] = left[i];  // 取出 right[i]，將它對應的左側樹位置設定為 left[i]
            if (left[i] != 0) i = left[i];  // 如果有左側樹，i 設定為 left[i]
            else i = right[i];  // 如果沒有左側樹，i 設定為 right[i]
        } else {  // 如果沒有砍樹，找右側樹
            i = right[i];  // i 設定為 right[i]
        }
        if (i > N) break;  // 如果 i > N，出界，中止 while 迴圈
    }
    
    cout << count << "\n" << imax << "\n";  // 印出答案
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`