[Codeforces] Round #536 B. Lunar New Year and Food Ordering

Lunar New Year and Food Ordering

https://codeforces.com/contest/1106/problem/B

考え方

題意

\( n \) 種類の料理 \( i \) のストックが \( a_i \) で、そのコストを \( c_i \) とします。

\( m \) 人のお客さんの \( i \) 番目の人が料理 \( t_i \) を \( d_i \) 個注文します。まず始めに、料理 \( t_i \) を提供します。料理 \( t_i \) のストックがなくなったとき、残っている料理の中で最もコストが低いものを提供します。コストが同じとき、種類番号の小さいものを選びます。もし、\( d_i \) 個の料理を提供できなかった場合は、コストが \( 0\) となりますが、既に料理は提供されたものとします。

このときのお客さんのそれぞれのコストを出力します。

方針

コスト順に整列されたキューを用います。また、料理のストックを管理する配列を用いて、キューの先頭を見たとき、在庫が \( 0 \) ならば、その要素を削除します。

コード

感想

実装力が試される問題だと思いました。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする