読者です 読者をやめる 読者になる 読者になる

AGC011 A Airport Bus:実装の解説

競プロ解説 atcoder

A: Airport Bus - AtCoder Grand Contest 011 | AtCoder

解法:早く着いた人からバスに乗せていけば良いです。
以下、実装のテク。

  • バスには必ず一人以上乗っている。そのバスの出発時刻は保存しておく。

とします。 始めに、1番目の人をバスに乗せます(まだ誰もバスに乗っていないので例外処理)

i番目の人について、今搭乗中のバスの出発時刻より

  • 後にi番目の人が到着するなら、今のバスは出発させて、新しいバスにその人を乗せる
  • 先にi番目の人が到着するなら、
    • バスがいっぱいなら、今のバスは出発させて、新しいバスにその人を乗せる
    • バスに空きがあるなら、今のバスに乗る

最後に、最後のバスを出発させる。(このバスには一人以上必ず乗っている)

Tのソートを忘れないようにしてください。

僕のコード:Submission #1156589 - AtCoder Grand Contest 011 | AtCoder
このコードだと出発時刻じゃなくて搭乗はじめの時間を保存してますがまあ大体同じです。