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)個の隙間の長さを加えたものが答え
別解法:ソート
- よく見るとpriority_queueに途中挿入はしていないので、ソートでも解ける
- 重要なのは「隙間の間隔0でも特別扱いしない」ことだろう