roiti46's blog

主に競プロ問題の解説を載せてます

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

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

問題はこちら

問題

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

  1. 手持ちのキャンディーを1つ、ある箱の中に加える。
  2. ある箱から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

まとめ

凹や凸のグラフの最小、最大値を求めるときにはすぐに三分探索を思いつけるようにならないとね。

広告を非表示にする