• 欢迎访问废江's博客 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏本站吧

Queue(任务题目)

AOJ 站点默认 6个月前 (04-05) 197次浏览 已收录 0个评论
文章目录[隐藏]

Question

Time Limit : 1 sec , Memory Limit : 131072 KB , isSolved :
There are n processes in a queue. Each process has namei and timei. The round-robin scheduling handles the processes in order. A round-robin scheduler gives each process a quantum (a time slot) and interrupts the process if it is not completed by then. The process is resumed and moved to the end of the queue, then the scheduler handles the next process in the queue.

For example, we have the following queue with the quantum of 100ms.

A(150) – B(80) – C(200) – D(200)
First, process A is handled for 100ms, then the process is moved to the end of the queue with the remaining time (50ms).

B(80) – C(200) – D(200) – A(50)
Next, process B is handled for 80ms. The process is completed with the time stamp of 180ms and removed from the queue.

C(200) – D(200) – A(50)
Your task is to write a program which simulates the round-robin scheduling.
Input
n q
name1 time1
name2 time2

namen timen
In the first line the number of processes n and the quantum q are given separated by a single space.

In the following n lines, names and times for the n processes are given. namei and timei are separated by a single space.

Output
For each process, prints its name and the time the process finished in order.

Constraints
1 ≤ n ≤ 100000
1 ≤ q ≤ 1000
1 ≤ timei ≤ 50000
1 ≤ length of namei ≤ 10
1 ≤ Sum of timei ≤ 1000000
Sample Input 1
5 100
p1 150
p2 80
p3 200
p4 350
p5 20
Sample Output 1
p2 180
p5 400
p1 450
p3 550
p4 800

Meaning

n是任务总个数,q是cpu完成某个任务不能超过的时间。给定一串任务,但是时间q长的任务不能一次完成,需要先存起来,进行后面的任务,等到一遍过后再回头完成之前的任务。用队列就ok了

Solution

这里我用的是我之前数据结构课自己写的队列代码

Coding

Summary

循环队列的关键实现:front=(front+1)%max rear=(rear+1)%max
队列中用elemtype来声明数据的好处是可以随题意改变来存储任何想要的数据形式
头文件:#include//malloc和free头文件,本地不加可以跑,但是一些oj不行

个人博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:Queue(任务题目)
喜欢 (0)
[]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到