Skip to content

Instantly share code, notes, and snippets.

@obelisk68
Last active April 27, 2020 23:40
Show Gist options
  • Save obelisk68/f8b2d586946e8c5f0ddeb0c6de328361 to your computer and use it in GitHub Desktop.
Save obelisk68/f8b2d586946e8c5f0ddeb0c6de328361 to your computer and use it in GitHub Desktop.
AOJ 0192: Multistory Parking Lot
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment