答えを二分探索

問題

$ N $ 台のプリンターがあり、$ 1 $ から $ N $ までの番号がつけられています。

プリンター $ i $ は $ A_i $ 秒ごとに１枚印刷できます。

つまりスイッチを入れてから $ A_i $ 秒後に１枚、$ 2A_i $ 秒後にもう１枚・・・と印刷可能です。

全てのプリンターのスイッチを同時に入れたとき、$ K $ 枚目が印刷されるのは何秒後でしょうか。

[制約]
🔹$ 1 \leqq N \leqq 100000 $
🔹$ 1 \leqq K \leqq 10^9 $
🔹$ 1 \leqq A_i \leqq 10^9 $
🔹答えは $ 10^9 $ 以下

解き方・ソースコード

この問題では、答えに対して二分探索を行うと効率的に解くことができます。

答えが１秒後から８秒後までのいずれかであると仮定してみます。

答えの候補の中央は４秒後ですので、答えが４秒以下かどうか？を考えます。

下記ソースの入力例を考えると、４秒後までに印刷される枚数は８枚であり $ K=10 $ 枚未満なので質問の答えはNoとなります。

この時点で、答えの候補が５秒後から８秒後までの範囲に絞られます。

この処理を探索範囲の左端(Left)と右端(Right)が同じになるまで繰り返します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#--------- 入力例 ----------
N = 4      # プリンターの数
K = 10     # 印刷したい枚数
A = [1, 2, 3, 4]
#----------------------------
# 答えがx以下かを判定し、YesであればTrue、No あればFalseを返す
def check(x, N, K, A):
    sum = 0
    for i in range(N):
        sum += x // A[i] # 「x ÷ A[i]」の小数点以下切り捨て
    print('{}秒後に印刷できる枚数は{}'.format(x, sum))
    if sum >= K:
        return True
    else:
        return False

# Left は探索範囲の左端、Right は探索範囲の右端を表す
Left = 1
Right = 10 ** 3
while Left < Right:
    Mid = (Left + Right) // 2
    Answer = check(Mid, N, K, A)

    if Answer == False:
        Left = Mid + 1  # 答えが Mid+1 以上である
    if Answer == True:
        Right = Mid     # 答えが Mid 以下である

# 出力（このとき Left=Right になっている）
print('解：', Left)

[実行結果]

500秒後に印刷できる枚数は1041

250秒後に印刷できる枚数は520

125秒後に印刷できる枚数は259

63秒後に印刷できる枚数は130

32秒後に印刷できる枚数は66

16秒後に印刷できる枚数は33

8秒後に印刷できる枚数は16

4秒後に印刷できる枚数は8

6秒後に印刷できる枚数は12

5秒後に印刷できる枚数は9

解： 6

この処理を繰り返すと6秒後に印刷される枚数が12枚となり、6秒後が正解となります。