寝癖頭の解法

学習中の覚え書きを投稿、更新していきます。

Aizu Online Judge in C #ALDS1_3_B Queue

Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。

・問題
f:id:neguse_atama:20200426164757p:plain
 ラウンドロビンスケジューリングと呼ばれる処理方法では、CPU がプロセスを順番に処理します。
 各プロセスは最大 q ms(これをクオンタムと呼びます)だけ処理が実行されます。
 q ms だけ処理を行っても、まだそのプロセスが完了しなければ、そのプロセスは列の最後尾に移動し、CPU は次のプロセスに割り当てられます。
 例えば、クオンタムを 100 msとし、次のようなプロセスキューを考えます。
 A(150) - B(80) - C(200) - D(200)
 まずプロセス A が 100 ms だけ処理され残りの必要時間 50 ms を保持しキューの末尾に移動します。
 B(80) - C(200) - D(200) - A(50)
 次にプロセス B が 80 ms だけ処理され、時刻 180 ms で終了し、キューから削除されます。
 C(200) - D(200) - A(50)
 次にプロセス C が 100 ms だけ処理され、残りの必要時間 100 ms を保持し列の末尾に移動します。
 D(200) - A(50) - C(100)
 このように、全てのプロセスが終了するまで処理を繰り返します。
 ラウンドロビンスケジューリングをシミュレートするプログラムを作成してください。

・入力される値
 入力の形式は以下の通りです。
f:id:neguse_atama:20200426164956p:plain
 最初の行に、プロセス数を表す整数 n とクオンタムを表す整数 q が1つの空白区切りで与えられます。
f:id:neguse_atama:20200426165119p:plain

・期待する出力
 プロセスが完了した順に、各プロセスの名前と終了時刻を空白で区切って1行に出力してください。

・条件
f:id:neguse_atama:20200426165219p:plain

僕が作成、提出したコードは、以下のとおりです。

/*
 ALDS1_3_B Queue
 http://judge.u-aizu.ac.jp/
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<stdio.h>
typedef struct{
    char name[11];
    int time;
}queue;
int main(void){
    int n,q;
    scanf("%d %d",&n,&q);
    int size=2*n;
    queue Queue[size];
    int pre=0,rear=0,cnt=0;
    for(rear=0;rear<n;++rear){
        scanf("%s %d",Queue[rear].name,&Queue[rear].time);
    }
    while(pre!=rear){
        if(Queue[pre].time<=q){
            cnt+=Queue[pre].time;
            printf("%s %d\n",Queue[pre].name,cnt);
        }else{
            cnt+=q;
            Queue[pre].time-=q;
            Queue[rear]=Queue[pre];
            rear=(rear+1)%size;
        }
        pre=(pre+1)%size;
    }
    return 0;
}

設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/
ALDS1_3_B Queue