ALDS1_3_B キューをC++で解いてみた[AIZU ONLINE JUDGE]

AIZU ONLINE JUDGE

こんにちは！ mnbd（@mnbbbbbd）です。

AIZU ONLINE JUDGEの「ALDS1_3_B キュー」を解いてみましたので、その回答と解説をご紹介いたします。

プログラミング初心者なので、もっといい回答があるに違いありません。

あくまでも「動作はする」サンプルとしてご覧ください。

Aizu Online Judge
onlinejudge.u-aizu.ac.jp

問題文

名前 namei と必要な処理時間 timei を持つ n 個のプロセスが順番に一列に並んでいます。ラウンドロビンスケジューリングと呼ばれる処理方法では、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)

このように、全てのプロセスが終了するまで処理を繰り返します。

ラウンドロビンスケジューリングをシミュレートするプログラムを作成してください。

入力
入力の形式は以下の通りです。
n q
name1 time1
name2 time2
...
namen timen

最初の行に、プロセス数を表す整数 n とクオンタムを表す整数 q が１つの空白区切りで与えられます。

続く n 行で、各プロセスの情報が順番に与えられます。文字列 namei と整数 timei は１つの空白で区切られています。

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

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/3/ALDS1_3_B

解答

#include <bits/stdc++.h>
using namespace std;

int const p_max = 100001;

struct process {
    string name;
    int time;
};

class Queue {
  private:
    process prc[p_max];
    int head;
    int tail;

  public:
    Queue() {
        head = 0;
        tail = 0;
    }

    void queue_print() {
        cout << endl;

        cout << "head:" << head << " tail:" << tail << endl;
        for(int i = head; i < tail; i++) {
            cout << "prc[" << i << "] " << prc[i].name << " " << setw(3)
                 << prc[i].time << endl;
        }
        cout << endl;
    }

    bool is_empty() {
        if(head == tail) {
            return true;
        } else {
            return false;
        }
    }
    bool is_full() {
        if(head >= p_max) {
            return true;
        } else {
            return false;
        }
    }
    void enqueue(process p) {
        if(is_full()) {
            cout << "Error:this queue is full.";
        }
        prc[tail] = p;
        if(tail + 1 == p_max) {
            tail = 0;
        } else {
            tail++;
        }
    }

    process dequeue() {
        if(is_empty()) {
            cout << "Error:this queue is empty.";
        }
        process p = prc[head];
        if(head + 1 == p_max) {
            head = 0;
        } else {
            head++;
        }
        return p;
    }
};

int main() {
    int n;
    int quant;
    cin >> n >> quant;
    int count = 0;
    process p[n];
    //process p[n] = {
    //    {"p1", 150}, {"p2", 80}, {"p3", 200}, {"p4", 350}, {"p5", 20}};
    for (int i = 0; i < n; i++) {
        cin >> p[i].name >> p[i].time;
    }
    Queue q;
    for(int i = 0; i < n; i++) {
        q.enqueue(p[i]);
    }

    int i = 0;
    while(!q.is_empty()) {
        process tmp = q.dequeue();
        if(quant < tmp.time) {
            q.enqueue({tmp.name, tmp.time - quant});
            count += quant;
        } else {
            count += tmp.time;
            cout << tmp.name << " " << count << endl;
        }
    }

    return 0;
}

感想

CPUのプロセス名と時間をどのように管理するか迷いました。

クラスとは別に構造体を使っていますが、C++的にこの書き方がいい書き方のかはわかりません。

そこは現状の自分の実力としては捨てています。

とりあえず動くことと合格することが最優先です。

その他にハマったポイントは、キューの配列数の確保のところで、数値が大きすぎると私の環境（MSYS2とgcc）では何も出力されませんでした。

エラーが出ないことでどこが悪いのかわからないのが難しいところです。

また、クラスの書き方に不備があるとデバッガ（gdb）がフリーズしてしまう問題も同様にエラーがでないのでハマってしまうと抜け出しにくくなります。

キュー構造については一般解説を読んで理解できればコード化しやすいと思います。

総じて文法でまだまだつまずいているといったところで道のりは長いです…。

まとめ

AIZU ONLINE JUDGEの「ALDS1_3_B キュー」を解いてみましたので、その回答と解説をご紹介いたしました。

少しずつですが、プログラミングの勉強をしています。
まだ初心者ですが、よかったらつながっていただけると嬉しいです。
Twitterアカウント（@mnbbbbbd）

以上です。
読んでいただきありがとうございました！

スポンサーリンク