キュー

Rubyアルゴリズムの勉強してます。 元ネタはプログラミングコンテスト攻略のためのアルゴリズムとデータ構造です。

class Proccezz
    attr_accessor :name, :t
    def initialize(name, t)
        @name = name
        @t = t
    end
end

class Queue
    LEN = 100005
    def initialize
        @head = 0
        @tail = 0
        @q = []
    end

    def enqueue(x)
        @q[@tail] = x
        @tail = (@tail + 1) % LEN
    end

    def dequeue
        x = @q[@head]
        @head = (@head + 1) % LEN
        x
    end

    def empty?
        @tail == @head
    end
end

def min(a, b)
    a < b ? a : b
end

elaps = 0
queue = Queue.new
n, q = gets.split(" ").map(&:to_i)
n.times do
    name, t = gets.split(" ")
    queue.enqueue Proccezz.new(name, t.to_i)
end

while ! queue.empty? do
    proc = queue.dequeue
    c = min(q, proc.t)
    proc.t -= c
    elaps += c
    if proc.t > 0
        queue.enqueue(proc)
    else
        puts "#{proc.name} #{elaps}"
    end
end