d030: 例題 P-3-6. 砍樹 (APCS202001)
Tags :
Accepted rate : 148人/169人 ( 88% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-03-29 16:29

Content

$N$ 棵樹種在一排,現階段砍樹必須符合以下的條件:「讓它向左或向右倒下,倒下時不會超過林場的左右範圍之外,也不會壓到其它尚未砍除的樹木。」

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

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

Input

第一行為正整數 $N$ 以及一個正整數 $L$,代表樹的數量與右邊界的座標;

第二行有 $N$ 個正整數代表這 $N$ 棵樹的座標,座標是從小到大排序的;

第三行有 $N$ 個正整數代表樹的高度。

同一行數字之間以空白間隔,$N \leq 10^5$,$L$ 與樹高都不超過 $10^9$。

Output

第一行輸出能被砍除之樹木數量,

第二行輸出能被砍除之樹木中最高的高度。

Sample Input #1
6 140
10 30 50 70 100 125
30 15 55 10 55 25
Sample Output #1
4
30
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <10M
公開 測資點#1 (20%): 1.0s , <10M
公開 測資點#2 (20%): 1.0s , <10M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
Hint :
Tags:
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」