プログラミングコンテストチャレンジブック演習「Expedition」

今回のお題はこちら。

これも発想の転換によって簡単に解けるようになる問題ですな。
Rubyには組み込みクラスでプライオリティキューが用意されていないようなのでArrayを使って実装しました。
が、これだと計算量がO(N^2logN)になるので不正解です。
自前でプライオリティキューを実装するのは面倒そうなのでチャレンジしていません。。

A = [10, 14, 20, 21] #input
B = [10, 5, 2, 4] #input
L = 25 #input
P = 10 #input

availableGSs = Array.new()
startPos = 0
endPos = P
count = 0

A.each_with_index do |a, i|
  availableGSs.push(B[i]) if startPos <= a && a <= endPos
end

until endPos >= L || availableGSs.length == 0
  A.each_with_index do |a, i|
    availableGSs.push(B[i]) if startPos <= a && a <= endPos
  end
  availableGSs.sort!{|a,b| b <=> a}
  gasoline = availableGSs.shift
  startPos += gasoline
  endPos += gasoline
  count += 1
end

if endPos < L
  puts -1
else
  puts count
end