身高高不一定比較厲害,個子矮的如果帶板凳可能會變高。有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。
5 5 4 1 1 3 0 0 4 0 1
6
最重要的重點是我們要維護一個單調遞減序列,既然是單調序列,就可以用二分搜找到第i個人站在板凳上的高度
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
95 |
110302@hshs....
(學生李侑霖)
|
a170 | 71 | 2024-07-18 00:15 |