olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

ピザ(09本選2)

円上にN個のピザ屋とM個の家があり、各家からの最も近いピザ屋までの距離の総和を求める問題。

愚直にやるとO(NM)で想定解法ではなさそうなので(10^9なので今は通るかもしれない)

二分探索をして各家がどのピザ屋とどのピザ屋の間にあるか調べる。

二分探索をする際に、先頭のピザ屋を一周した先にも置いておくと楽。

(ピザ屋の情報に0とDを加える)

計算量がO(MlogN)なので通る。

難易度は6程度であるように感じた。

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