Chặt Nhị Phân Kết Quả - Đốn Gỗ Tối Ưu (EKO Woodcutters)
Một người đốn gỗ cần thu hoạch ít nhất M mét gỗ từ một hàng gồm N cây gỗ có chiều cao lần lượt là H1, H2, …, HN.
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: Monotonic Functions, Binary Search.
Nội dung đề bài
Mô tả bài toán
Một người đốn gỗ cần thu hoạch ít nhất M mét gỗ từ một hàng gồm N cây gỗ có chiều cao lần lượt là H1, H2, …, HN.
Máy cưa của anh ta hoạt động như sau: thiết lập một độ cao lưỡi cưa nguyên H. Lưỡi cưa sẽ cắt ngang tất cả các cây cao hơn H ở độ cao H, và thu hoạch được phần ngọn vượt quá H. Các cây có chiều cao ≤ H sẽ giữ nguyên. Tổng số mét gỗ thu được là: ∑i=1N max(0LL, Hi - H)
Hãy tìm độ cao nguyên H lớn nhất có thể để tổng lượng gỗ thu được đạt ít nhất M mét.
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc
stdinvà in rastdout. Bài này không yêu cầu viết hàm. - Không dùng
coutđể in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vàostdoutvà làm bài sai. - Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
- Dòng đầu chứa hai số nguyên N và M (1 ≤ N ≤ 106, 1 ≤ M ≤ 2 · 109).
- Dòng thứ hai chứa N số nguyên H1, H2, …, HN (1 ≤ Hi ≤ 109).
Output
- In ra một số nguyên duy nhất: độ cao tối đa của lưỡi cưa H.
Ràng buộc
- Thời gian chạy tối đa: 1000ms.
- Giới hạn bộ nhớ: 256MB.
- Dữ liệu đầu vào tuân thủ đúng định dạng và miền giá trị được mô tả.
Ví dụ 1
Input
4 7
20 15 10 17Output
15Giải thích
Dữ liệu kiểm thử mẫu và kết quả thực thi theo yêu cầu.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.