# Codility: Fish 魚
在一條河流中,有 N
隻飢腸轆轆的魚。題目會給予兩個長度為 N
(N > 0
)的整數陣列 A
和 B
,代表從上游開始往下第 i
(0 <= i < N
)隻魚的大小 A[i]
以及游泳方向 B[i]
,每隻魚的大小及位置都不會相同。魚的游泳方向只會是 0
或是 1
,分別代表:
0
代表魚往上游的方向游1
代表魚往下游的方向游
如果相鄰的魚(兩隻魚中間沒有活著的魚)朝對方的方向游泳的話,他們就會相遇。這時候就只剩下一隻魚會活下來,也就是體型比較大的魚會把比較小的魚吃掉。更確切的說,假設有兩隻魚 P
和 Q
,其中 P < Q
、B[P] = 1
、B[Q] = 0
、P
和 Q
中間沒有任何活魚的時候,他們就會相遇,相遇之後:
- 如果
A[P] > A[Q]
的時候 P 就會把 Q 吃掉,然後 P 繼續往下游前進 - 如果
A[P] < A[Q]
的時候 P 就會被 Q 吃掉,然後 Q 繼續往上游前進
在這個題目中,你可以假設魚在河裡的游泳速度全部都一樣(不管什麼方向)。換句話說,朝同一個方向游的魚絕對不會相遇。你的目標就是計算最後剩下幾隻魚。
# 測資說明
1 <= N <= 100000
,N
是整數- 陣列
A
中的每個元素1 <= A[i] <= 1000000000
,A[i]
是不重複的整數, - 陣列
B
中的每個元素0 <= B[i] <= 1
,B[i]
是整數
# 範例
假設給定以下資料:
A = [4, 3, 2, 1, 5]
B = [0, 1, 0, 0, 0]
一開始所有的魚都是活著的,除了 1
號魚以外其他都是往上游的方向游泳。接下來:
- 1 號魚和 2 號魚會相遇,然後 2 號魚被吃掉
- 1 號魚和 3 號魚會相遇,然後 3 號魚被吃掉
- 1 號魚和 4 號魚會相遇,然後 1 號魚被吃掉
- 最後會剩下 0 號魚和 4 號魚,他們永遠不會相遇