Bedao Mini Contest 21 - Cắt dây
Xem dạng PDF
Cho ~n~ sợi dây, sợi dây thứ ~i~ có độ dài ~A_i~ đơn vị độ dài. Giả sử có một sợi dây độ dài ~X~, nếu ta cắt một đoạn độ dài ~0 < t < X~ thì ta sẽ được hai sợi dây mới độ dài ~t~ và ~X - t~.
Được thực hiện ~k~ phép cắt dây, hãy tìm độ dài nhỏ nhất có thể của sợi dây dài nhất nhé.
Input
Dòng đầu chứa hai số nguyên dương ~n~ và ~k~ ~(1 \le n \le 2 \times 10^5, 0 \le k \le 10^9)~, thể hiện số lượng sợi dây và số lượng phép cắt thực hiện.
Dòng thứ hai chứa ~n~ số nguyên dương ~A_1, A_2, ..., A_n~ ~(1 \le A_i \le 10^9)~ - độ dài ban đầu của ~n~ sợi dây.
Output
Gọi ~S~ là độ dài nhỏ nhất của sợi dây dài nhất, có thể cắt được sau ~k~ phép cắt dây. In ra giá trị ~S~ làm tròn lên đến phần nguyên.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~20~ | ~k = 1~ |
| 2 | ~30~ | ~n, A_i \le 1000~ |
| 3 | ~50~ | Không có ràng buộc gì thêm |
Sample Input 1
5 1
3 3 3 4 5
Sample Output 1
4
Sample Input 2
2 3
7 9
Sample Output 2
4
Notes
Trong test ví dụ thứ hai, ta có thể thực hiện lần lượt các phép cắt như sau:
Với sợi dây độ dài ~7~, ta có thể cắt ra thành hai sợi dây độ dài ~\frac{7}{2}~.
Với sợi dây độ dài ~9~, ta có thể cắt ra thành hai sợi dây độ dài ~3~ và ~6~.
Với sợi dây độ dài ~6~, ta có thể cắt ra thành hai sợi dây độ dài ~3~.
Vậy sợi dây có độ dài lớn nhất là ~\frac{7}{2}~, ta cần in ra giá trị làm tròn lên là ~4~. Ta có thể chứng minh đây là phương án tối ưu.
Bình luận
chào các bạn, mình hiều nhầm "làm tròn lên đến phần nguyên" thành "làm tròn đến phần nguyên"
đừng như mình
ai gthich de bai voi a, nghe kho hieu qua
My solve: