AOJ 0192: Multistory Parking Lot

aoj_0192.rb

class Car
  num = 1
  
  define_method(:initialize) do |wait_time:|
    @num = num
    num += 1
    @wait_time = wait_time
  end
  attr_reader :num, :wait_time
  
  def next_minute
    @wait_time -= 1
  end
  
  define_singleton_method(:clear) {num = 1}
end

class ParkingLot
  Space = Struct.new(:upper, :lower)
  
  def initialize(num)
    @spaces = num.times.map {|i| Space.new}
  end
  attr_reader :spaces
  
  def add_car(new_car)
    idx = @spaces.index {|sp| sp.lower.nil?}
    if idx
      @spaces[idx].lower = new_car   #下のスペースが空いている
    else
      return false if @spaces.all?(&:upper)    #満車
      
      #下は空いていないが満車でない場合
      idxs = @spaces.map.with_index {|sp, i| sp.upper ? nil : i}.compact
      idx = idxs.map {|i|
        diff = @spaces[i].lower.wait_time - new_car.wait_time
        diff >= 0 ? [diff, i] : nil
      }.compact.sort.first&.last
      unless idx
        idx = idxs.map {|i| [new_car.wait_time - @spaces[i].lower.wait_time, i]}
                  .sort.first.last
      end
      
      @spaces[idx].upper = @spaces[idx].lower
      @spaces[idx].lower = new_car
    end
    true
  end
  
  def cars_go_out
    out = []
    
    2.times do
      @spaces.each do |sp|
        if sp.lower && sp.lower.wait_time <= 0
          out << sp.lower.num
          sp.lower = sp.upper
          sp.upper = nil
        end
      end
    end
    
    out
  end
  
  #車庫が空か
  def empty?
    @spaces.all? {|sp| sp.lower.nil?}
  end
end

class TimeManegement
  def initialize(cars, pl)
    @time = 0
    @from_somewhere = cars
    @pl = pl
    @entrance = []
    
    class << @from_somewhere
      def car_comes
        shift
      end
    end
    
    class << @entrance
      def car_enters
        shift
      end
      
      def restore(car)
        unshift(car)
      end
    end
  end
  
  def next_minute
    @time += 1
    
    #駐車スペースにある車の残りの駐車時間を一分減らす
    @pl.spaces.each do |sp|
      sp.lower&.next_minute
      sp.upper&.next_minute
    end
  end
  
  def cars_go_out
    @pl.cars_go_out
  end
  
  def car_comes
    @entrance << @from_somewhere.car_comes if next_car_comes?
    
    while (new_car = @entrance.car_enters)
      unless @pl.add_car(new_car)
        @entrance.restore(new_car)    #満車の場合
        break
      end
    end
  end
  
  def end?
    @pl.empty?
  end
  
  private
  
  def next_car_comes?
    (@time % 10).zero? && !@from_somewhere.empty?
  end
end


until (given = gets.split.map(&:to_i)) == [0, 0]
  Car.clear
  
  m, n = given
  cars = n.times.map {Car.new(wait_time: gets.to_i)}
  
  pl = ParkingLot.new(m)
  tm = TimeManegement.new(cars, pl)
  
  result = []
  
  loop do
    result += tm.cars_go_out
    tm.car_comes
    break if tm.end?
    tm.next_minute
  end
  
  puts result.join(" ")
end