競技プログラミング用 知識集積所
ABC410B - Reverse Proxy
最終更新：
sport_programming
-
view
問題
必要知識
A問題レベルのものは省略
考え方
ボールの番号は実はあまり関係がない。
ということは、各箱の中に入っているボールの個数だけ管理すればよい。
ということは、各箱の中に入っているボールの個数だけ管理すればよい。
数列の指示が1以上の場合は、入れる箱はそのまま指定の箱でよい。
数列の指示が0だった場合は、入れる箱を探しに行くことになる。
これは「いまのところの最小値とその位置」を保持しながら前から順に全ての値をチェックする全探索（未作成）でよい。
このとき、最小値と同じ値が重ねて出てきた場合は最小値位置を更新しないこと。
これは「いまのところの最小値とその位置」を保持しながら前から順に全ての値をチェックする全探索（未作成）でよい。
このとき、最小値と同じ値が重ねて出てきた場合は最小値位置を更新しないこと。
入れる箱がわかったら、それを出力して、その番号の箱の中身数を1増やす。
これらをループの中に入れてしまえばよい。
これらをループの中に入れてしまえばよい。
解答例
注意点
0始まりにする場合に0番指定がずれることに注意。
問題の入力では、箱番号が1始まりとなっているが、vectorの添え字は0始まりである。
この問題を回避するのに全部から1を引いておくというのがよく使われる手法。
しかし、今回は0という入力も存在しているので、これの扱いを注意しなければならない。
一番単純な方法は、-1とあったら0番の指示と判断すること。
この問題を回避するのに全部から1を引いておくというのがよく使われる手法。
しかし、今回は0という入力も存在しているので、これの扱いを注意しなければならない。
一番単純な方法は、-1とあったら0番の指示と判断すること。
0始まりにしない場合に最小値の取り方に注意。
問題の入力では、箱番号が1始まりとなっているが、vectorの添え字は0始まりである。
この問題を回避するのにvectorをn+1個用意して0番の箱を無意味に置いておくというのもよく使われる手法。
しかし、最小値を取るときにうっかり0番の箱を巻き込むと最小値位置を間違える。
最小値を1番の箱から考えるようにするか、0番に十分大きな値を入れておくこと。
この問題を回避するのにvectorをn+1個用意して0番の箱を無意味に置いておくというのもよく使われる手法。
しかし、最小値を取るときにうっかり0番の箱を巻き込むと最小値位置を間違える。
最小値を1番の箱から考えるようにするか、0番に十分大きな値を入れておくこと。
別解
distance()（未作成）とmin_element()（未作成）を使う
vecの中の最小値の位置は
distance(vec.begin(), min_element(vec.begin(),vec.end()));
