キュー
キューを用いてラウンドロビンによるスケジューリングをシミュレートし、キューの内容が変わるたびにその内容を出力しなさい。最後にプロセスが完了したら、各プロセス名と終了時刻を空白で区切って終了した順に1行で出力し改行して終了すること。ラウンドロビンスケジューリングでは、CPUが列の先頭のプロセスをクオンタム q ms だけ実行する。q ms 実行してもそのプロセスが完了しなければ、そのプロセスは列の最後尾に移動する。
入力
・最初の行にプロセス数を表す整数 n とクオンタムを表す整数 q
・続く n 行で各プロセスの名前(文字列)と必要な処理時間(整数)の組
出力
・プロセスが完了した順に各プロセスの名前と終了時刻を空白で区切って1行に出力
・最後にプロセスが完了したら、各プロセス名と終了時刻を空白で区切って終了した順に1行で出力し改行して終了
制約
1 ≦ n ≦ 100000, 1 ≦ q ≦ 1000, 1 ≦ 各プロセスの必要処理時間 ≦ 50000, 全プロセスの合計時間 ≦ 1000000
入力例1:
2 100
p1 150
p2 70
出力例1:
p2 70 p1 50
p1 50
p2 170 p1 220
(改行して終了)
入力・出力例1の解説:
最初に列の先頭にある p1 を 100ms 実行するが終わらないため、p1は列の最後尾に移動する。このときにキューの内容が変わるため内容を出力する(p2 70 p1 50)。続いてp2 を実行し、クアンタム以内に終了すると p1 のみがキューに残るという形でキューの内容が変わるため再び内容を出力する(p1 50)。最後に p1 の残りを実行して完了し、その際に各プロセス名と終了時刻を終了した順に出力して終了する(p2 170 p1 220)。
入力例2:
3 100
p1 200
p2 50
p3 150
出力例2:
p2 50 p3 150 p1 100
p3 150 p1 100
p1 100 p3 50
p3 50
p2 150 p1 350 p3 400
(改行して終了)
入力・出力例2の解説:
最初に列の先頭にある p1 を 100ms 実行するが終わらないため、p1は列の最後尾に移動する。このときにキューの内容が変わるため内容を出力する(p2 50 p3 150 p1 100)。続いてp2 を実行し、クアンタム以内に終了してキューの内容が変わるため内容を出力する(p3 150 p1 100)。続いて p3 を 100ms 実行するが終わらないため、p3は列の最後尾に移動し、このときにキューの内容が変わるため内容を出力する(p1 100 p3 50)。続いて p1 の残りを実行し、クアンタム以内に終了してキューの内容が変わるため内容を出力する(p3 50)。最後に p3 の残りを実行して完了し、その際に各プロセス名と終了時刻を終了した順に出力して終了する(p2 150 p1 350 p3 400)。
解答は以下になります。
#include <stdio.h> #include <stdlib.h> #include <string.h> int main(void){ int n,q,data[10000],m=10; int i=0,len; char name[10000][10000]; char countname[10000][10000]; int countdata[10000]; int counttime=0; scanf("%d %d",&n, &q); for (i=0;i<n;i++){ scanf("%s %d",&name[i], &data[i]); len++; } for (m=0;m<101;m++){ rotate(data,name,n,q,&len,countdata,countname,&counttime); } for (i=0;i<n;i++){ printf("%s %d",countname[i],countdata[i]); } return 0; } void rotate(int data[], char name[10000][10000], int n, int q, int *len,int countdata[10000], char countname[10000][10000],int *counttime){ int startdata = data[0]; char startname[10000]; strcpy(startname, name[0]); int i; if (data[0] > q){ for(i=0;i<n-1;i++){ data[i] = data[i+1]; strcpy(name[i],name[i+1]); } *counttime += q; data[n-1] = startdata-q; strcpy(name[n-1],startname); }else{ for(i=0;i<n-1;i++){ data[i] = data[i+1]; strcpy(name[i],name[i+1]); } countdata[n-*len] = *counttime + startdata; strcpy(countname[n-*len],startname); *counttime += q; *len = *len -1; } for (i=0;i<*len;i++){ printf("%s %d\n",name[i],data[i]); } return; }