문제
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.
제약 조건
1 ≤ machines ≤ 200,000. Each time and the target are between 1 and 1,000,000,000. The answer fits signed 64-bit.
예시
입력:
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;설명
At time 6 the machines have made 3 + 2 = 5 items. At time 5 they have made only 2 + 1 = 3.
입력:
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;설명
One machine completes its third item at 3 × 4 = 12 seconds.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
For any chosen time, you can count how many items all machines together would finish by then.
힌트 2
The answer is the earliest time where that produced count reaches the target.
힌트 3
A monotonic condition like this is well suited to searching over time instead of simulating production.
예상 복잡도
O(n log T) time, O(1) extra space
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.