yukicoder No.198 キャンディー・ボックス２

★2だが手間取ってしまった・・・。

問題

キャンディーボックスがN箱あり箱iにはキャンディーがC_i個入っている。あなたにはいま手持ちのキャンディーがB個あり、次の2つ操作によってすべてのキャンディーボックスのキャンディーの数を等しくしたい。

手持ちのキャンディーを1つ、ある箱の中に加える。
ある箱から1つキャンディーを抜きさり、手持ちに加える。

持てるキャンディーの数に制限はないとする。
すべてのキャンディーボックスのキャンディーを等しくするのに必要な操作回数の最小値を求めよ。

解法

必要な操作回数のグラフは下に凸になるので、三分探索で解ける。
最終でのキャンディーボックス内のキャンディー数を探索していく。範囲が2より大きい間は、適当な2点での必要な操作数を比較して範囲を狭めていく。ただし、キャンディーボックス内に加えるキャンディーの数が手持ちのキャンディーを超えていないか確認することを忘れないようにする。

B = int(raw_input())
N = int(raw_input())
C = [int(raw_input()) for i in xrange(N)]

ans = 10**18
l, r = -1, 10**18
while r - l > 2:
    lm, rm = (2 * l + r) / 3, (l + 2 * r) / 3
    if   sum(lm - c for c in C) > B:
        r = lm
    elif sum(rm - c for c in C) > B:
        r = rm
    elif sum(abs(lm - c) for c in C) <= sum(abs(rm - c) for c in C):
        r = rm
    else:
        l = lm

print sum(abs((r + l) / 2 - c) for c in C)

本番では三分探索を思いつけず、次のように解いた。
まず二分探索で最終のキャンディーボックスのキャンディー数の上限を探索する。あとは、その値に合わせるのに必要な個数と、初期の各キャンディーボックスのキャンディー数に合わせるのに必要な個数を比較して、最小値を計算していた。キャンディーを加えるのと抜きさる操作が同じ1回なので、これでも答えは得られる。

B = int(raw_input())
N = int(raw_input())
C = [int(raw_input()) for i in xrange(N)]

ans = 10**18
l, r = -1, 10**18
while r - l > 1:
    m = (l + r) / 2
    b = sum(m - c for c in C)
    if b > B:
        r = m
    else:
        l = m
        ans = min(ans, sum(abs(m - c) for c in C))

for ci in C:
    if sum(ci - c for c in C) > B: continue
    ans = min(ans, sum(abs(ci - c) for c in C))
print ans