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
Solution
这里我用的是我之前数据结构课自己写的队列代码
Coding
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
//自己写的队列(数组实现) //因为非循环队列太耗空间了,我就直接写循环队列,其实区别很小,要注意的就两点: //利用求余操作就可以实现:front=(front+1)%max rear=(rear+1)%max //例外需要注意的数组必须留一个空间,不能存满,为了方便判断队列满和队列空的情况 //要写的操作有 : 初始化队列 :initqueue , 销毁队列: destroyqueue , 判断为空: emptyqueue // 进队列 enqueue , 出队列 dequeueu 打印队列 printqueue #include<iostream> #include<string> #include<cstdio> #include<stdlib.h>//malloc和free头文件,本地不加可以跑,但是一些oj不行 #define maxsize 100005 using namespace std; //typedef char elemtype;//之前不喜欢这样写,觉得太麻烦了,后来我想把int换成char去写字符串匹配的时候,就爱上了这样的写法 //这里data不能再是字符串了,需要一个结构数组来存储每个任务 typedef struct{ char name[100]; int time; }elemtype; typedef struct{ elemtype data[maxsize]; int front,rear; }squeue; void initqueue(squeue*&q){ q=(squeue*)malloc(sizeof(squeue)); q->front=q->rear=0; } void destroyqueue(squeue*&q){ free(q); } bool emptyqueue(squeue*q){ return (q->front==q->rear); } bool enqueue(squeue*&q,elemtype e){ if((q->rear+1)%maxsize==q->front) return false; q->rear=(q->rear+1)%maxsize; q->data[q->rear]=e; return true; } bool dequeue(squeue*&q,elemtype &e){ if(q->rear==q->front) return false; q->front=(q->front+1)%maxsize; e=q->data[q->front];//因为队列中必须空一个数,空的数我们让front指向 return true; } void printqueue(squeue*q){ int pre=q->front; while(pre!=q->rear){ pre=(pre+1)%maxsize; cout << q->data[pre].name << " " << q->data[pre].time << endl; } cout<<endl; } long long sum;//总时间记录变量 squeue *qu; int main(){ initqueue(qu);//声明队列放外面,初始化放在里面 elemtype e; int n,q; cin>>n>>q; //先给所有任务进队列 for(int i=0;i<n;i++){ scanf("%s",&e.name); scanf("%d",&e.time); enqueue(qu,e); } while(!emptyqueue(qu)){ dequeue(qu,e); if(e.time<=q){ sum+=e.time; cout<<e.name<<" "<<sum<<endl; }else{ sum+=q; e.time-=q; enqueue(qu,e); } } } |
Summary
队列中用elemtype来声明数据的好处是可以随题意改变来存储任何想要的数据形式
头文件:#include