Problem 1027 --数据结构-队列-循环调度程序

1027: 数据结构-队列-循环调度程序

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 53  Solved: 32
[Submit][Status][Web Board][Creator:]

Description

队列中有n个进程。 每个进程都有名字和时间, 循环调度按顺序处理进程。 循环调度程序为每个进程提供一个时隙(一段非常短的时间),并在该进程尚未完成时中断该进程并移动到队列末尾,然后调度器处理队列中的下一个进程。

例如,我们有以下(时隙为100ms)进程的队列。

 A(150)-B(80)-C(200)-D(200)
首先,进程A被处理100ms,然后进程被移动到剩余时间(50ms)的队列末尾。
B(80)-C(200)-D(200)-A(50)
接下来,进程B处理80ms。 该进程完成(完成时间点100+80)并从队列中移除。 C(200)-D(200)-A(50)
你的任务是编写一个模拟循环调度的程序  

Input

n q
name1 time1
name2 time2
...

namen timen

在第一行中,进程个数n和时隙被一个空格分开。在下面的n行中,给出了n个进程的名称和时间。 名字时间被一个空格隔开。

  • 1≤n≤100000
  • 1≤q≤1000
  • 1≤ 时间 ≤50000
  • 1≤ 名称长度≤10
  • 1≤ 时间之和≤1000000

Output

对于每个进程,按顺序打印其名称和流程完成的时间。

Sample Input

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

Sample Output

p2 180
p5 400
p1 450
p3 550
p4 800

Source

[Submit][Status]