Codility: Fish 魚

在一條河流中,有 N 隻飢腸轆轆的魚。題目會給予兩個長度為 NN > 0)的整數陣列 AB,代表從上游開始往下第 i0 <= i < N)隻魚的大小 A[i] 以及游泳方向 B[i],每隻魚的大小及位置都不會相同。魚的游泳方向只會是 0 或是 1,分別代表:

  • 0 代表魚往上游的方向游
  • 1 代表魚往下游的方向游

如果相鄰的魚(兩隻魚中間沒有活著的魚)朝對方的方向游泳的話,他們就會相遇。這時候就只剩下一隻魚會活下來,也就是體型比較大的魚會把比較小的魚吃掉。更確切的說,假設有兩隻魚 PQ,其中 P < QB[P] = 1B[Q] = 0PQ 中間沒有任何活魚的時候,他們就會相遇,相遇之後:

  • 如果 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. 1 號魚和 2 號魚會相遇,然後 2 號魚被吃掉
  2. 1 號魚和 3 號魚會相遇,然後 3 號魚被吃掉
  3. 1 號魚和 4 號魚會相遇,然後 1 號魚被吃掉
  4. 最後會剩下 0 號魚和 4 號魚,他們永遠不會相遇