d033. Q_3_5 帶著板凳排雞排的高人 (APCS201902)
Tags : ch3
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-08-10 22:31

Content

 身高高不一定比較厲害,個子矮的如果帶板凳可能會變高。有 $n$ 個人排隊買雞排,由前往後從 $1 \sim n$ 編號,編號 $i$ 的身高為 $h_i$ 而他帶的板凳高度為 $p_i$。
若 $j$ 在 $i$ 之前且 $j$ 的身高大於 $i$ 站在自己板凳上的高度,也就是說 $h_j > h_i+p_i$,則 $j$ 是 $i$ 的「無法超越的位置」,若 $j$ 是 $i$ 最後的無法超越位置,則兩人之間的人數 $(i-j-1)$ 稱為 $i$ 的「最大可挑戰人數」$S(i)$;如果 $i$ 沒有無法超越位置,則最大可挑戰人數 $S(i)=i-1$也就是排在他之前全部的人數。

舉例來說,假設 $n=5$ ,身高 $h$ 依序為 $(5, 4, 1, 1, 3)$ 而板凳高度 $p$ 依序是 $(0, 0, 4, 0, 1)$。計算可得 $h_i+p_i=(5, 4, 5, 1, 4)$,編號 $1$ 的人前面沒有人,所以 $1$ 的最大可挑戰人數$S(1) = 0$。對編號 $2$ 的人而言,$h_2+p_2= 4$,而往前看到第一個大於 $4$ 的是 $h_1=5$,所以 $S(2)=2–1–1=0$。而 $h_3+p_3 =5$,前面沒有人的身高大於 $5$,所以 $S(3)=2$。而$h_4+p_4=1$, $h_2 = 4 > 1$,所以位置 $2$ 是 $4$ 的無法超越位置,$S(4)=4–2–1=1$。同理可求出 $S(5)=3$,他的不可超越位置是 $1$ 的身高 $5$。

輸入 $h$ 與 $p$,請計算所有人 $S(i)$ 的總和。

Input

第一行為 $n$,$n ≤ 2 \times 10^5$;
第二行有 $n$ 個正整數,依序是 $h_1 \sim h_n$;
第三行有 $n$ 個非負整數,依序代表是 $p_1 \sim p_n$;

數值都不超過 $10^7$,同一行數字之間都是以空白間隔。

Output

 輸出 $S(i)$ 的總和。答案可能超過 $2^{32}$,但不會超過 $2^{60}$。

Sample Input #1
5
5 4 1 1 3
0 0 4 0 1
Sample Output #1
6
測資資訊:
記憶體限制: 256 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
Hint :

本題與P-3-4的主要差異是多了板凳高度,另外有個小差異是計算的值略有不同。例題的題解中最重要的重點是我們只要維護一個單調遞減序列,既然是單調序列,就可以用二分搜找到第i個人站在板凳上的高度。此外,例題中我們介紹了另外一種使用multimap的解法,一樣可以稍作修改後解此題。

Tags:
ch3
出處:
Prof. Wu [管理者: ktlai (K.我已霸榜.Tlai) ]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」