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
公開 測資點#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
提示 ：
標籤:
出處:
2020年1月APCS
[管理者：
ktlai@cmgsh.
...
(賴楷宗)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 34923 |
|
h028 | 515 | 2023-04-27 08:35 | |
| 29222 |
|
h028 | 1441 | 2022-02-07 12:43 |