身高高不一定比較厲害,個子矮的如果帶板凳可能會變高。有 $n$ 個人排隊買雞排,由前往後從 $1$ 到 $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)$ 的總和。
第一行為 $n$ , $n ≤ 2 \times 10^5$
第二行有 $n$ 個正整數,依序是 $h(1)$ ~ $h(n)$
第三行有 $n$ 個非負整數,依序代表是 $p(1)$ ~ $p(n)$ ;數值都不超過$10^7$,同一行數字之間都是以空白間隔。
輸出 $S(i)$ 的總和。答案可能超過 $2^32$,但不會超過 $2^60$。
5 5 4 1 1 3 0 0 4 0 1
6
8 1 2 2 3 4 4 3 1 0 0 0 0 0 0 0 0
15
本題與P-3-4的主要差異是多了板凳高度,另外有個小差異是計算的值略有不同。例題的題解中最重要的重點是我們只要維護一個單調遞減序列,既然是單調序列,就可以用二分搜找到第i個人站在板凳上的高度。
ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |