AtCoder ABC B - AtCoder Amusement Park (6Q, 灰色, 200 点)

繰り返し回数を計算する必要もない、本当に愚直なシミュレーション！

• 問題へのリンク

問題概要

人乗りのゴンドラアトラクションに対して、 組のグループが待機している。グループ の人数は 人である ( が保証される)。

各グループに対して、順に

• グループ人数が、今いるゴンドラの残席数以下の場合は、グループ全員を乗せる
• そうでない場合は、ゴンドラを発射させて、次のゴンドラに乗せる

待機列全員分について、ゴンドラを何回発射させるかを求めよ。

解法

問題文に書かれた通りのシミュレーションをしよう！

「最後のゴンドラ」を発射させるのを忘れないように注意しよう。

コード

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

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    
    // シミュレーション
    int res = 0;  // 発射回数
    int already = 0;  // 今ストップしているゴンドラに乗っている人数
    for (int i = 0; i < N; ++i) {
        if (already + A[i] <= K) {
            // まだ A[i] 人乗れるなら乗せる
            already += A[i];
        } else {
            // A[i] 人を乗せられないならゴンドラを発射させて、
            ++res;
            
            // 次のゴンドラに乗せる
            already = A[i];
        }
    }
    
    // 最後のゴンドラを発射する
    ++res;
    
    // 出力
    cout << res << endl;
}