h028. 202001_3 砍樹
標籤 : APCS
通過比率 : 607人/774人 ( 78% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-01-24 16:39

內容

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

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

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

輸入說明

第一行為正整數 $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 分: 無額外限制。
輸出說明

輸出共有兩行,第一行輸出能被砍除之樹木數量,第二行輸出能被砍除之樹木中最高的高度,如果無法砍除任何一棵樹,則最高高度輸出 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
測資資訊:
記憶體限制: 512 MB
提示 :
標籤:
APCS
出處:
2020年1月APCS [管理者: ktlai@cmgsh. ... (賴楷宗) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
41422 glps1004@gma ... (Ian) h028
APCS 202001全解析
213 2024-07-25 12:03
34923 luray0601@gm ... (QWERTYPIG) h028
C++題解(含想法)
865 2023-04-27 08:35
29222 bubble60324@ ... (賢仔) h028
新手的解題想法
1733 2022-02-07 12:43