최소 시간
골드 IV의견: 0
공장에 \(m\)대의 기계가 있고, 처리해야 할 똑같은 작업이 \(N\)개 있다. \(i\)번째 기계는 작업 한 개를 처리하는 데 정확히 \(a_i\)분이 걸리며, 멈추지 않고 작업을 이어서 처리한다. 따라서 \(T\)분 동안 \(i\)번째 기계는 \(\left\lfloor T / a_i \right\rfloor\)개의 작업을 끝낸다.
모든 기계는 동시에(병렬로) 일을 시작한다. \(N\)개의 작업을 모두 끝내기까지 걸리는 최소 시간(분)을 구하여라. 즉, 끝난 작업 수의 합이 처음으로 \(N\) 이상이 되는 가장 작은 정수 \(T\)이다.
\(1 \le m \le 100\,000\), \(0 \le N \le 10^{18}\), \(1 \le a_i \le 10^9\). 정답은 64비트 정수 범위 안에 들어간다.
첫째 줄에 기계의 수 \(m\)과 작업의 수 \(N\)이 공백으로 구분되어 주어진다. 둘째 줄에 \(m\)개의 정수 \(a_1, \ldots, a_m\)이 공백으로 구분되어 주어진다.
\(N\)개의 작업을 모두 끝내는 데 필요한 최소 시간을 출력한다.
2 5
2 3
6
\(6\)분이면 기계 1은 \(6/2=3\)개, 기계 2는 \(6/3=2\)개, 합 \(5\)개로 \(5\)개를 채운다. \(5\)분이면 \(2+1=3\)개뿐이다.
1 7
1
7
기계가 하나뿐이고 한 개당 \(1\)분이므로 \(7\)개에 \(7\)분이 든다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
최소 시간
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
최소 시간