ALDS1_3_B: Queue
この問題は『プログラミングコンテストのためのアルゴリズムとデータ構造(渡部有隆著,Ozy・秋葉拓哉協力)』を読んで解きました.
問題
- URL: キュー | アルゴリズムとデータ構造 | Aizu Online Judge
- 要約: キューを用いて各プロセスが終了(ラウンドロビンスケジューリング)したら,プロセス名と経過時間を出力せよ
ソースコード
- AOJ: AIZU ONLINE JUDGE: Code Review
- GitHub: AOJ/ALDS1_3_B_Queue.c at master · canon4444/AOJ · GitHub
- ソースコード:
#include <stdio.h> // キューの構造体 typedef struct { char name[11]; int time; } Queue; int main() { //入力 int n, q; scanf("%d%d", &n, &q); int size = 2 * n; //キューのサイズ Queue Queue[size]; int pre = 0, rear = 0, cnt = 0; //pre:enqueue, rear:inqueue, cnt:経過時間 for( rear = 0; rear < n; ++rear ) scanf("%s %d", Queue[rear].name, &Queue[rear].time); //処理と出力 while( pre != rear ){ if( Queue[pre].time <= q ){ // if( Queue[pre].time == q ){ inqueueしない } cnt += Queue[pre].time; printf("%s %d\n", Queue[pre].name, cnt); } else { cnt += q; Queue[pre].time -= q; Queue[rear] = Queue[pre]; //inqueue rear = (rear + 1) % size; //次のinqueue先 } //次のdequeue先 pre = (pre + 1) % size; } return 0; }
反省点
- 入力を配列にしてぐるぐる回したら終了条件に困って全部の要素を確認したらTLE
- 素直にキューを実装
- ↑↑残り要素数を把握していれば良かったかもしれないけれど,問題がキューなのでキューを実装しましょう