AOJ ALDS1_3_B Queue

備忘録

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_B&lang=ja

回答

import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque
import copy

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, Q = il()
    que = queue.Queue()
    process_end = []

    for n in range(N):
        name, time = sl()
        que.put([name, int(time)])

    end_time = 0
    while not que.empty():
        name, time = que.get()
        if time > Q:
            end_time += Q
            que.put([name, time - Q])
        else:
            end_time += time
            process_end.append([name, end_time])

    for p in process_end:
        print(*p)


if __name__ == '__main__':
    main()

考え方

queueを用いてFIFOの規則で処理を行う。

与えられたキューを先頭から順に処理にかかる時間とくクオンタムの比較を行う。
処理を完了することができる場合には回答用の配列に追加、
処理が完了しない場合には、残りの時間と一緒にキューへ再度入れる。

あとはキューが全て無くなるまで上記の処理をループさせることで、
回答を得ることができる。