h028. 202001_3 砍樹 - 高中生程式解題系統

內容

有一個長度為 $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
公開測資點#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

提示：

標籤:

APCS

出處:

2020年1月 APCS [管理者： ktlai@cmgsh.tp.edu.tw

ktlai@cmgsh. ... (賴楷宗) ]

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