APCS202001 第3題砍樹

作業上傳：http://203.68.236.9/problem/c0201

zerojudge題目：https://zerojudge.tw/ShowProblem?problemid=h028

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

 若 ci 代表第 i 棵樹的位置座標，hi 代表高度。向左倒下壓到的範圍為 [ci−hi,ci]，而向右倒下壓到的範圍為 [ci,ci+hi]。 如果倒下的範圍內有其它尚未砍除的樹就稱為壓到，剛好在端點不算壓到。 我們可以不斷找到滿足砍除條件的樹木，將它砍倒後移除，然後再去找下一棵可以砍除的樹木，直到沒有樹木可以砍為止。

無論砍樹的順序為何，最後能砍除的樹木是相同的。

輸入說明

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

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

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

本題包含三個子題組，每個子題組配分如下： 

第 1 子題組共 20 分： N≤10 

第 2 子題組共 40 分： N≤1000 

第 3 子題組共 40 分： 無額外限制。

輸出說明

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

輸入範例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

解題策略

由左到右掃描所有樹，將不可移除的樹加入堆疊。考慮新的樹，如果堆疊內有可以移除(向右倒下，連鎖反應)的樹就移除，接著檢查新的樹是否可以移除(向左倒下，此時向右倒下可以暫時不考慮)，可以就移除，否則加入堆疊，直到檢查所有樹為止。