Stove (AOJ)

Quiz

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0647

他人の解法

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3593831#1

説明

  • 例えば4人来客、マッチ3本の場合、1つの隙間部分は点けっぱなしにする必要がある
  • 隙間の間隔は小さいものを選びたい
  • N人来客の場合、N-1の隙間ができる(間隔0でも隙間と考える)
  • priority_queueに隙間を入れることで、小さい方から取り出せる
  • 来客中のN秒は点けることが確定で、それに(N-K)個の隙間の長さを加えたものが答え

別解法:ソート