Cắt gỗ

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Người đăng:
Dạng bài

Nông dân Jonh cần phải cắt M mét gỗ để đem về làm chuồng bó cho đàn bò của mình. Bác có một cái máy cắt gỗ mới, vì vậy mà công việc chặt gỗ cũng chở lên dễ dàng hơn. Tuy nhiên, bác Jonh chỉ được phép để cắt các cây gỗ thành một hàng duy nhất. Máy cắt gỗ của bác Jonh hoạt động như sau: bác thiết lập một tham số chiều cao H (tính bằng mét), và máy sẽ cắt toàn bộ các cây có chiều cao lớn hơn H (tất nhiên, cây không cao hơn H mét vẫn còn nguyên vẹn). Sau đó bác chỉ chọn những phần cây bị cắt đứt. Ví dụ, nếu hàng cây chứa cây với chiều cao là 20, 15, 10, và 17 mét, và bác Jonh thiết lặp chiều cao là 15 mét, chiều cao các cây còn lại sau khi cắt sẽ là 15, 15, 10, và 15 mét, khi đó bác Jonh sẽ nhặt 5 mét của cây đầu tiên và 2 mét của cây thứ tư và có tổng số là 7 mét gỗ. Bác Jonh là người tiết kiệm, vì vậy bác không muốn cắt gỗ nhiều hơn cần thiết. Vì vậy bác muốn thiết lập cho máy của mình chiều cao H càng cao càng tốt. Trợ giúp bác Jonh tìm số nguyên chiều cao tối đa của chiều cao H đề bác vẫn có thể cắt ít nhất là M mét gỗ.

INPUT: WOOD.INP

  • Dòng đầu tiên chứa 2 số nguyên dương N (1 ≤ N ≤ 10^6) là số lượng cây gỗ và M (1 ≤ M ≤ 2*10^9) là tổng độ dài mét gỗ cần khai thác.
  • Dòng thứ hai chứa N số nguyên dương (nhỏ hơn 10^9) là chiều cao của mỗi cây gỗ (tính bằng mét). Dữ liệu vào luôn đảm bảo là bác Jonh có thể cắt được M mét gỗ.

OUTPUT: WOOD.OUT

  • Một dòng duy nhất là chiều cao H lớn nhất cần thiết lập.

*

inp

4 7

20 15 10 17

out

5 20

4 42 40 26 46

inp

5 

out

36


Bình luận

Hãy đọc nội quy trước khi bình luận.


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