【AtCoder】ABC 410 B - Reverse Proxy | 緑コーダーが解くAtCoder

atcoder.jp

配点: 200 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 57 / NoviSteps: 6Q

問題概要
制約
考察
実装例
コメント

問題概要

空の箱が $N$ 個あり、これから $Q$ 個のボールを数列 $X$ に従って箱に入れていく。具体的には、 $i$ 番目のボールに次の処理を行う。

$X_i \geq 1$ のとき : このボールを箱 $X_i$ に入れる。
$X_i = 0$ のとき : このボールを、現在入っているボールが最も少ない箱のうち番号が最小である箱に入れる。

それぞれのボールをどの箱に入れたかを求めよ。

制約

入力は全て整数
$1 \le N, Q \le 100$
$0 \le X_i \le N$

考察

制約が小さいので、 $X_i = 0$ のときも愚直にfor文を使ってボールの個数が最小の箱を見つければよい。

答えを出力するときは、 $X_i = 0$ の箇所を書き換えつつ、配列 $X$ の値を順次出力するのが簡単。

実装例

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

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

constexpr int INF = 1e+9;

template <typename T>
inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

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

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

    vector<int> boxes(N + 1, 0);
    rep(i, 0, Q)
    {
        if (X[i] >= 1)
        {
            boxes[X[i]]++;
        }
        else
        {
            int idx = -1, cnt = INF;
            rep(j, 1, N + 1)
            {
                if (chmin(cnt, boxes[j]))
                {
                    idx = j;
                }
            }

            boxes[idx]++;
            X[i] = idx;
        }
    }

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

    return 0;
}