Queue(任务题目）

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

//自己写的队列（数组实现）
//因为非循环队列太耗空间了，我就直接写循环队列，其实区别很小，要注意的就两点：
//利用求余操作就可以实现：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

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

废江博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 转载请注明原文链接：Queue(任务题目）