AOJ 0231 （Dangerous Bridge : 危ない橋）

【問題】

https://onlinejudge.u-aizu.ac.jp/problems/0231

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

【解説】

1秒ごとにシミュレーションしていく方法では、時刻の最大値が2^31のため到底間に合わないため、工夫する必要がある。

まず、橋が壊れるかどうかは橋の上に載っている通行人の総重量のみで決まる。総重量が変動する要素は、「通行人が橋に乗る」「通行人が橋から降りる」場合しかないため、各通行人が橋に乗る時刻と橋から降りる時刻のみ管理すればよい。

そのため、各通行人が橋に乗った時刻と降りた時刻を、時刻の昇順にソートし、乗った時点で通行人の体重を総重量に加え、降りた時点で通行人の体重を総重量から減じていき、いずれかの時点で耐えられる強度の150kgを超えるかどうかを判定すればよい。ソートのコストをO（n^2）としても、実行時間はO（n^2 +n）であり、nは高々100であるため十分制限実行時間内に間に合う計算量となる。

なお、ソート時に「通行人が橋に乗る」「通行人が橋から降りる」イベントが同時に発しする場合、先に橋から降りるイベントを処理する必要がある点に注意する。

【コード】