a173:
P-3-6. 砍樹
內容
N
棵樹種在一排，現階段砍樹必須符合以下的條件：「讓它向左或向右倒下，倒下時不會超過林場的左右範圍之外，也不會壓到其它尚未砍除的樹木。」。
你的工作就是計算能砍除的樹木。
若c[i]代表第i棵樹的位置座標，h[i]代表高度。
向左倒下壓到的範圍為[c[i]-h[i],c[i]]，而向右倒下壓到的範圍為[c[i],c[i]+h[i]]。
如果倒下的範圍內有其它尚未砍除的樹就稱為壓到，剛好在端點不算壓到。
我們可以不斷找到滿足砍除條件的樹木，將它砍倒後移除，然後再去找下一棵可以砍除的樹木，直到沒有樹木可以砍為止。
無論砍樹的順序為何，最後能砍除的樹木是相同的。
輸入說明
第一行為正整數N以及一個正整數L，代表樹的數量與右邊界的座標；
第二行有N個正整數代表這N棵樹的座標，座標是從小到大排序的；
第三行有N個正整數代表樹的高度。
同一行數字之間以空白間隔，N≤1e5，L與樹高都不超過1e9。
輸出說明
第一行輸出能被砍除之樹木數量，第二行輸出能被砍除之樹木中最高的高度
範例輸入
#1
6 140 10 30 50 70 100 125 30 15 55 10 55 25
範例輸出
#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
公開 測資點#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
提示 ：
標籤:
出處:
AP325
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||