h028: 202001_3 砍樹
Tags : APCS
Accepted rate : 73人/110人 ( 66% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-04-25 22:41

Content

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

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

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

Input

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

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

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

 

本題包含三個子題組,每個子題組配分如下:

  • 第 1 子題組共 20 分: $N \leq 10$
  • 第 2 子題組共 40 分: $N \leq 1000$
  • 第 3 子題組共 40 分: 無額外限制。
Output

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

Sample Input #1
6 140
10 30 50 70 100 125
30 15 55 10 55 25
Sample Output #1
4
30
Sample Input #2
1 10
5
6
Sample Output #2
0
0
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 0.5s , <1K
公開 測資點#2 (5%): 0.5s , <1K
公開 測資點#3 (5%): 0.5s , <1K
公開 測資點#4 (5%): 0.5s , <1M
公開 測資點#5 (5%): 0.5s , <1M
公開 測資點#6 (5%): 0.5s , <1M
公開 測資點#7 (5%): 0.5s , <1M
公開 測資點#8 (5%): 0.5s , <1M
公開 測資點#9 (5%): 0.5s , <1M
公開 測資點#10 (5%): 0.5s , <1M
公開 測資點#11 (5%): 0.5s , <1M
公開 測資點#12 (5%): 0.5s , <10M
公開 測資點#13 (5%): 0.5s , <10M
公開 測資點#14 (5%): 0.5s , <10M
公開 測資點#15 (5%): 0.5s , <10M
公開 測資點#16 (5%): 0.5s , <10M
公開 測資點#17 (5%): 0.5s , <10M
公開 測資點#18 (5%): 0.5s , <10M
公開 測資點#19 (5%): 0.5s , <10M
Hint :
Tags:
APCS
出處:
2020年1月APCS [管理者:
ktlai@cmgsh.... (賴楷宗)
]


ID User Problem Subject Hit Post Date
29222
bubble60324@... (賢仔)
h028
新手的解題想法
235 2022-02-07 12:43