Tốc độ đọc sách tối thiểu

Trung bình

tìm kiếm nhị phân trên đáp án5 test · 3 giây

Minh có n cuốn sách, cuốn thứ i dày aᵢ trang, và phải đọc xong tất cả trong h giờ. Mỗi giờ Minh chọn một cuốn và đọc tối đa k trang của cuốn đó (đọc hết cuốn mà còn dư thời gian thì nghỉ, không chuyển sang cuốn khác).

Tìm k nhỏ nhất để đọc xong đúng hạn.

Nhận xét: k càng lớn càng dễ đạt → tìm kiếm nhị phân trên đáp án.

Dữ liệu vào

Dòng 1: n h (1 ≤ n ≤ 10⁵, n ≤ h ≤ 10⁹).

Dòng 2: n số nguyên (1 ≤ aᵢ ≤ 10⁹).

Dữ liệu ra

Số k nhỏ nhất.

Ví dụ

Input

4 8
3 6 7 11

Output

Input

5 5
30 11 23 4 20

Output

Bài tiếp theo: Gộp các khoảng chồng nhau →

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

Input (stdin)

Output

Bấm “Chạy thử” để xem kết quả với input bên trái.