Xây chuồng cao tầng

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bác nông dân John đang xây một chuồng bò gồm $N$ tầng, với sự giúp đỡ của $K$ con bò. Mỗi con bò phải được phân công vào đúng một tầng, và mỗi tầng phải có ít nhất một con bò.

Tầng thứ $i$ cần $a_{i}$ đơn vị công việc để hoàn thành. Nếu có $c$ con bò được phân công vào tầng $i$ , thời gian để hoàn thành tầng đó là $a_{i} / c$ giờ.

Các tầng phải được xây tuần tự (tầng $i$ phải xong trước khi bắt đầu tầng $i + 1$ ), nên tổng thời gian là tổng thời gian hoàn thành từng tầng.

Hãy xác định tổng thời gian tối thiểu để xây xong chuồng bò, với cách phân bổ bò tối ưu.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $K$ .
$N$ dòng tiếp theo, dòng thứ $i$ chứa giá trị $a_{i}$ .

Dữ liệu ra

In ra tổng thời gian tối thiểu, làm tròn đến số nguyên gần nhất.

Dữ liệu đầu vào được đảm bảo rằng đáp án cách giá trị nguyên gần nhất hơn $0.1$ .

Ràng buộc

$1 \leq N \leq K \leq 10^{12}$
$N \leq 10^{5}$
$1 \leq a_{i} \leq 10^{12}$

Ví dụ

Input	Output	Giải thích
2 5 10 4	5	Phân bổ 4 bò cho tầng 1 và 1 bò cho tầng 2. Thời gian = $10 / 4 + 4 / 1 = 2.5 + 4 = 6.5$ . Tuy nhiên phân bổ 3 bò tầng 1, 2 bò tầng 2 cho thời gian $10 / 3 + 4 / 2 \approx 3.33 + 2 = 5.33$ . Phân bổ tối ưu cho kết quả làm tròn là $5$ .
4 7 2 10 5 1	9	Có 4 tầng và 7 con bò, mỗi tầng cần ít nhất 1 bò. Phân bổ tối ưu 3 bò còn dư cho các tầng có khối lượng công việc lớn nhất.

Ghi chú

Lưu ý rằng $K$ có thể rất lớn (đến $10^{12}$ ), nên thuật toán tham lam thông thường (thêm từng bò một) sẽ không đủ nhanh.

Bình luận

Không có bình luận tại thời điểm này.