In tài liệu

Binary-search Buổi 13 — Chặt nhị phân đáp án greedy
Points
11
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Văn phòng có $N$ máy in hoạt động song song. Máy in thứ $i$ cần $t_i$ giây để in xong $1$ trang tài liệu. Cần in tổng cộng $K$ trang tài liệu (các máy in có thể bắt đầu cùng lúc tại thời điểm $0$).

Hãy tìm thời gian tối thiểu (tính bằng giây) để hoàn thành việc in ít nhất $K$ trang.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $K$.
  • Dòng thứ hai chứa $N$ số nguyên $t_1, t_2, \dots, t_N$.
Dữ liệu ra

In ra thời gian tối thiểu cần thiết.

Ví dụ
Input Output
3 7

3 2 5 | 8 | | 1 5 4 | 20 |

Giới hạn
  • $1 \le N \le 10^5$
  • $1 \le K \le 10^9$
  • $1 \le t_i \le 10^9$.
Draft saved