返回列表 發帖

帶著板凳排雞排的高人 (AP325 Q-3-5)

身高高不一定比較厲害,個子矮的如果帶板凳可能會變高。有 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 ≤ 2e5;第二行有 n 個正整數,依序是 h(1)~h(n);第三行有 n 個非負整數,依序代表是 p(1)~p(n);數值都不超過 1e7,同一行數字
之間都是以空白間隔。
輸出:輸出 S(i)的總和。答案可能超過 2^32,但不會超過 2^60。

範例輸入:
5
5 4 1 1 3
0 0 4 0 1

範例結果:
6

返回列表