工場の生産完了時間

工場の生産完了時間

複数の機械が目標個数を最速で生産できる時刻を求めてください。

このチャレンジで学べること

すべての機械は時刻0から独立して稼働を開始します。ある機械の生産時間が t 秒の場合、t 秒後に1個目、2t 秒後に2個目、…というように生産します。複数の機械の合計生産数が目標に達する最も早い整数秒を求めてください。

factory_machines(times, target) を実装してください。

times: 各機械が1個生産するのに必要な秒数のリスト。

target: 必要な完成品の個数。

最小の経過秒数を返してください。

1 ≤ machines ≤ 200,000。各生産時間および目標個数は1以上1,000,000,000以下。答えは符号付き64ビット整数に収まります。

例 1

入力：
times = [2, 3]
target = 5

期待される出力：
expected = 6

入力：
std::vector<long long> times = {2, 3};
long long target = 5;

期待される出力：
long long expected = 6;

入力：
long[] times = new long[] {2, 3};
long target = 5;

期待される出力：
long expected = 6;

時刻6では、機械は合計3 + 2 = 5個生産しています。時刻5では、合計2 + 1 = 3個しか生産していません。

例 2

入力：
times = [4]
target = 3

期待される出力：
expected = 12

入力：
std::vector<long long> times = {4};
long long target = 3;

期待される出力：
long long expected = 12;

入力：
long[] times = new long[] {4};
long target = 3;

期待される出力：
long expected = 12;

1台の機械が3個目を完成させるのは 3 × 4 = 12 秒後です。

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

ある時間を決めたら、その時点までに全機械で何個作れるか数えられます。

ヒント 2

答えは、作成数が目標に届く最小の時間です。

ヒント 3

このような単調な条件は、実際に生産をシミュレーションするより時間で二分探索するのに向いています。

目安の計算量

時間 O(n log T)、追加メモリ O(1)

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。