【AtCoder】ABC 358 B - Ticket Counter | 茶コーダーが解くAtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 43

問題概要

1つのチケット売り場があり、来園客はこのチケット売り場の前に一列に並んで順にチケットを購入する。チケットの購入手続きには一人当たり $A$ 秒かかり、列の先頭の人がチケットを購入し終わると、 (存在すれば) 次の人がすぐさま購入手続きを開始する。現在チケット売り場に並んでいる人はおらず、今から $N$ 人の人が順にチケットを買いに来る。具体的には、 $i$ 番目の人は今から $T_i$ 秒後にチケット売り場を訪れ、既に列が存在すればその最後尾に並び、存在しなければすぐさま購入手続きを開始する。各 $i$ について、 $i$ 番目の人がチケットを購入し終わるのは今から何秒後か求めよ。

制約

入力はすべて整数。
$1 \leq N \leq 100$
$0 \leq T_1 < T_2 < \cdots < T_N \leq 10^6$
$1 \leq A \leq 10^6$

考察

問題文が少々複雑だが、冷静に考えれば時系列順に処理するだけである。

まず、時間を記録する変数timeを持っておき、T[1]に初期化。あとは以下の処理を行えばよい。
各 $i \: (1 \leq i \leq N)$ について、

$\mathrm{time} < T_i$ のとき (列がすでに存在しているとき) のみ、 $\mathrm{time}$ を $T_i$ に更新 (前の人の手続きが終わるまで待機) 。
常に、 $\mathrm{time}$ に $A$ を加算する (手続き処理をする) 。
このときのtimeを出力する。

なお、コードでは 0-indexed になっていることに注意。

コード

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

using ll = long long;

// ======================================== //

int main()
{
    int N, A;
    cin >> N >> A;
    vector<int> T(N);
    rep(i, 0, N) cin >> T[i];

    vector<ll> ans(N);
    ll time = T[0];
    rep(i, 0, N)
    {
        if (time < T[i])
            time = T[i];

        time += A;
        ans[i] = time;
    }

    for (auto &&x : ans)
    {
        cout << x << endl;
    }
}