e153: 感應燈
Tags : greedy sortings
Accepted rate : 1人/4人 ( 25% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-09-20 07:32

Content

  現在有 盞不同格局的燈,編號為 1~N ,對於每一盞燈,假設燈的編號為 i,那麼該盞燈將擁有「持續時間 ti 分鐘」,代表你只要打開了該盞燈,這盞燈就會持續亮著 t分鐘;更準確地說,假設你在第 分鐘打開了這盞燈,那麼燈在第 k, k+1, ... , k + ti -1 這些分鐘都會是亮的。

  不過,有些燈已經被打開過了,現在是第 分鐘,而第 盞燈恰好在 ai 分鐘前就被打開了,看似肥宅的駿豪看著這 盞燈,他覺得那些暗著的燈實在太醜了,他決定想辦法讓亮著的燈盡量多,然後再拍下一張美麗的照片。

  可惜,駿豪的體能有點差,這讓他只能在每一分鐘打開一盞燈,又或者是他可以選擇不要開燈跑去重設一盞燈的持續時間(也就是說,假設他在第 分鐘重設了第 盞燈,那麼接下來在第 k, k+1, ... , k + t-1 這些分鐘第 盞燈也還會是亮的),無論如何,每分鐘內他就只能辦到其中一件事,也可以什麼都不做。

  你可以告訴駿豪,若他要選擇一個分鐘拍照的話,在經過一連串最佳的開燈/重設時間的順序後,他最多可以拍到同時有多少燈是開著的呢?

Input

首行輸入一個整數 N (1 ≤ N ≤ 2 • 10) 。

次行有 個整數 a1 ~ aN (-1 ≤ ai < ti  以空格隔開,其中若 ai = -1,代表該盞燈在 0 分鐘時是關著的。

第三行 個整數 t1 ~ tN ( 1 ≤ ti ≤  109) 以空格隔開。

Output

輸出經過一連串最佳的開燈/重設時間的順序後,最多可以有多少燈是同時開著的。

Sample Input
輸入範例一
2
-1 -1
2 3
輸入範例二
5
-1 -1 -1 -1 1
1 2 3 5 4
Sample Output
輸出範例一
2
輸出範例二
5
測資資訊:
記憶體限制: 256 MB
不公開 測資點#0 (3%): 1.0s , <50M
不公開 測資點#1 (3%): 1.0s , <1M
不公開 測資點#2 (3%): 1.0s , <1M
不公開 測資點#3 (3%): 1.0s , <1M
不公開 測資點#4 (3%): 1.0s , <1M
不公開 測資點#5 (3%): 1.0s , <1M
不公開 測資點#6 (3%): 1.0s , <1M
不公開 測資點#7 (3%): 1.0s , <1M
不公開 測資點#8 (3%): 1.0s , <50M
不公開 測資點#9 (3%): 1.0s , <50M
不公開 測資點#10 (3%): 1.0s , <50M
不公開 測資點#11 (3%): 1.0s , <50M
不公開 測資點#12 (3%): 1.0s , <50M
不公開 測資點#13 (3%): 1.0s , <50M
不公開 測資點#14 (3%): 1.0s , <1M
不公開 測資點#15 (3%): 1.0s , <1M
不公開 測資點#16 (4%): 1.0s , <1M
不公開 測資點#17 (4%): 1.0s , <1M
不公開 測資點#18 (4%): 1.0s , <1M
不公開 測資點#19 (4%): 1.0s , <1M
不公開 測資點#20 (4%): 1.0s , <1M
不公開 測資點#21 (4%): 1.0s , <1M
不公開 測資點#22 (4%): 1.0s , <1M
不公開 測資點#23 (4%): 1.0s , <1M
不公開 測資點#24 (4%): 1.0s , <50M
不公開 測資點#25 (4%): 1.0s , <50M
不公開 測資點#26 (4%): 1.0s , <50M
不公開 測資點#27 (4%): 1.0s , <50M
不公開 測資點#28 (4%): 1.0s , <50M
Hint :

比賽測資範圍 N ≤ 2 • 105 ,O(NogN)滿分,此為加強版,AC 要 O(N)

日後仍有可能變動測資,若題敘或測資有問題歡迎寄信。

 

本題共有七組測試題組,條件限制如下所示。每一組可有一或多筆測試資料。

子任務

額外輸入限制

e153_00

ai = -1,ti 接相異.

e153_01 - e153_03

N ≤ 1000,ai = -1.

e153_04 - e153_07

N ≤ 5 • 104,ai = -1.

e153_08- e153_13

ai = -1.

e153_14 - e153_18

N ≤ 1000

e153_19 - e153_23

N ≤ 5 • 104

e153_24 - e153_28

無特別限制。

 

Tags:
greedy sortings
出處:
108學年度板橋高中校內資訊學科能力競賽Day2_pD310573sao [管理者:
310573sao (Jiburiru)
]


ID User Problem Subject Hit Post Date
19254
310573sao (Jiburiru)
e153
賽後題解
139 2019-09-20 20:33