JOI難易度６ ピザ

問題原文

https://www.ioi-jp.org/joi/2008/2009-ho-prob_and_sol/2009-ho.pdf#page=4

問題要旨

長さ の円環上に 個の店舗がある。（入力で与えられるのは 個で、店舗０は座標０にある） また注文が 個きており、円環状の宅配場所が与えられる。
各注文について最も近い店舗から宅配するとき、全注文を処理する場合の総宅配距離はいくらになるか？

• 
• 
• 

解法

各注文について最も近い店舗を二分探索で求めればよい。
D=8、宅配場所=7, 店舗１= 5 のような時は、そのまま進んで店舗０に届ける方が近くなるように処理する必要があるが、店舗 = となるようなものを追加しておけば問題なく処理できる。

実装

Pythonだと A[-1] みたいなことがなまじできてしまってREでなくWAを吐くケースがあるので注意すること。
S[i - 1] が S[-1] になるケースですね。

from bisect import bisect_left
D = int(input())
N = int(input())
M = int(input())
S = [0] + sorted([int(input()) for _ in range(N - 1)]) + [D]
K = [int(input()) for _ in range(M)]


ans = 0
for k in K:
    i = bisect_left(S, k)
    ans += max(0, min(S[i] - k, k - S[i - 1]))

print(ans)

感想

Pythonのスライスは便利だけどこういう時は十分注意する。