问题 4952 --伐树(cut)

4952: 伐树(cut)

题目描述

  李老板需要总长为 M 米的木材,他安排光头强去砍树。树林里有 N 棵树,为了保护环境,不能将一个树完全砍掉,会留出一部分,因为这样树还可以继续生长。光头强将他的砍树装置的锯片高度设置为 H 米,这样可以锯掉所有的树比 H 高的部分。求在得到 M 米木材的前提下, HH 的最大值。
比如,一共有 4 棵树,高度分别为 20、15、8、17,需要 6 米的木材,若将锯片的高度设置为 15 米,这样可以得到的木材为 5+0+0+2=7 米,若锯片的高度提高 1 米,设置为 16 米,只能得到木材的长度 4+1=5 。为了得到 6 米的木材,锯片的高度最大只能设置为 15 米。

输入

第一行,两个整数 N 和 M 。
第二行,N 个整数,表示每棵树的高度

输出

  一个整数,意义如上所述。

样例输入输出

输入#1 复制
4 6
20 15 8 17
输出#1 复制
15

提示

$1 \leq N \leq 100000$
$1 \leq M< 2^{31}$ 
保证所有树的总长度不小于 M

序号 标题 作者 发表时间 费用 订购数 操作