今回のお題はこちら。
これも発想の転換によって簡単に解けるようになる問題ですな。
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