a170: Q-3-5. 帶著板凳排雞排的高人
標籤 : APCS201902
通過比率 : 33人/40人 ( 82% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-11-09 14:03

內容

身高高不一定比較厲害,個子矮的如果帶板凳可能會變高。有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)的總和。答案可能超過232,但不會超過260

範例輸入 #1
5
5 4 1 1 3
0 0 4 0 1
範例輸出 #1
6
測資資訊:
記憶體限制: 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
提示 :

最重要的重點是我們要維護一個單調遞減序列,既然是單調序列,就可以用二分搜找到第i個人站在板凳上的高度

標籤:
APCS201902
出處:
AP325 [管理者: ]


編號 身分 題目 主題 人氣 發表日期
95
110302@hshs.... (學生李侑霖)
a170
nice
71 2024-07-18 00:15