読者です 読者をやめる 読者になる 読者になる

ALDS1_3_B: Queue

この問題は『プログラミングコンテストのためのアルゴリズムとデータ構造(渡部有隆著,Ozy・秋葉拓哉協力)』を読んで解きました.

 

問題

 

ソースコード

#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
  • 素直にキューを実装
  • ↑↑残り要素数を把握していれば良かったかもしれないけれど,問題がキューなのでキューを実装しましょう