한정판 쿠키 공장
실버 II의견: 0
한정판 쿠키 \(M\)개의 주문이 들어왔다. 공장에는 오븐이 \(N\)대 있는데, \(i\)번째 오븐은 \(t_i\)분마다 쿠키를 정확히 \(1\)개씩 구워 낸다. 즉 시각 \(t_i, 2t_i, 3t_i, \dots\)에 쿠키가 하나씩 완성된다.
다만 오븐마다 전용 반죽이 한정되어 있어서, \(i\)번째 오븐은 최대 \(c_i\)개까지만 구울 수 있다. 따라서 \(T\)분 동안 \(i\)번째 오븐이 굽는 쿠키 수는 \(\min(c_i, \lfloor T / t_i \rfloor)\)개이다.
모든 오븐을 동시에 가동할 때, 쿠키를 \(M\)개 이상 완성하는 데 필요한 시간의 최솟값(분)을 구하여라.
- \(1 \le N \le 100\,000\)
- \(1 \le t_i \le 10^9\)
- \(1 \le c_i \le 10^6\)
- \(1 \le M \le c_1 + c_2 + \dots + c_N\) (즉 답은 항상 존재한다)
첫째 줄에 오븐의 수 \(N\)과 주문량 \(M\)이 공백으로 구분되어 주어진다.
다음 \(N\)개의 줄에 걸쳐 \(i\)번째 줄에 \(t_i\)와 \(c_i\)가 공백으로 구분되어 주어진다.
쿠키 \(M\)개를 완성하는 최소 시간을 분 단위로 출력한다.
2 4
3 2
2 3
6
\(6\)분이 지나면 첫 오븐이 \(\min(2, 6/3)=2\)개, 둘째 오븐이 \(\min(3, 3)=3\)개를 구워 총 \(5\)개가 된다. \(5\)분까지는 \(1+2=3\)개뿐이다.
1 7
5 10
35
오븐이 하나뿐이므로 \(7\)개를 구우려면 \(5 \times 7 = 35\)분이 필요하다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
한정판 쿠키 공장
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
한정판 쿠키 공장