队列调度 (Queue)

​时间限制​: 1 秒 ​内存限制​: 131072 KB

题目描述

有 n 个进程排成一个队列。每个进程有一个名称 name_i 和执行所需的时间 time_i（单位：毫秒）。

采用轮转调度算法Round-Robin Scheduling来处理这些进程。调度器会依次处理队列中的进程，并为每个进程分配一个固定的时间片（quantum，单位：毫秒）。

处理规则如下：

1. 调度器从队首取出一个进程，执行时间片长度的任务。
2. 如果该进程​在时间片内完成​，则记录它的完成时间并从队列中移除；
3. 如果该进程​未完成​，则将它的剩余时间更新后，放到队列末尾，等待下一个调度周期。

示例说明

设时间片 q = 100 ms，队列如下：

A(150) - B(80) - C(200) - D(200)

• ​第一步​： 处理 A 100ms，剩余 50ms，移到队尾：

  B(80) - C(200) - D(200) - A(50)
  

• ​第二步​： 处理 B 80ms，B 完成，结束时间为 180ms，移出队列：

  C(200) - D(200) - A(50)
  

• 按此方式持续执行，直到所有进程完成。

输入格式

n q
name1 time1
name2 time2
...
namen timen

• 第一行：两个整数 n 和 q，表示进程数量和时间片长度；
• 接下来 n 行：每行一个进程的 name_i（不超过 10 个字符）和 time_i（正整数）。

输出格式

对于每个进程，按其完成顺序输出：

name finish_time

• name：进程名称
• finish_time：进程完成的时间（单位：毫秒）

数据范围

样例输入 1

5 100
p1 150
p2 80
p3 200
p4 350
p5 20

样例输出 1

p2 180
p5 400
p1 450
p3 550
p4 800