Đề bài
All machines start at time 0 and work independently. A machine with time t finishes one item after t seconds, another after 2t seconds, and so on. Find the earliest whole second when their combined production reaches the target.
Implement factory_machines(times, target).
Input
times: Seconds needed for one item on each machine.
target: The number of completed items required.
Output
Return the minimum elapsed seconds.
Ràng buộc
1 ≤ machines ≤ 200,000. Each time and the target are between 1 and 1,000,000,000. The answer fits signed 64-bit.
Ví dụ
Đầu vào:
times = [2, 3]
target = 5
Kết quả mong đợi:
expected = 6Đầu vào:
std::vector<long long> times = {2, 3};
long long target = 5;
Kết quả mong đợi:
long long expected = 6;Đầu vào:
long[] times = new long[] {2, 3};
long target = 5;
Kết quả mong đợi:
long expected = 6;Giải thích
At time 6 the machines have made 3 + 2 = 5 items. At time 5 they have made only 2 + 1 = 3.
Đầu vào:
times = [4]
target = 3
Kết quả mong đợi:
expected = 12Đầu vào:
std::vector<long long> times = {4};
long long target = 3;
Kết quả mong đợi:
long long expected = 12;Đầu vào:
long[] times = new long[] {4};
long target = 3;
Kết quả mong đợi:
long expected = 12;Giải thích
One machine completes its third item at 3 × 4 = 12 seconds.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
For any chosen time, you can count how many items all machines together would finish by then.
Gợi ý 2
The answer is the earliest time where that produced count reaches the target.
Gợi ý 3
A monotonic condition like this is well suited to searching over time instead of simulating production.
Độ phức tạp mong đợi
O(n log T) time, O(1) extra space
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.