砍树

课程自编 · 二分答案

题目描述

有 $n$ 棵树，第 $i$ 棵树的高度为 $h_i$。选择一个整数锯口高度 $H$，把所有高于 $H$ 的部分锯下，得到的木材总量为 $\sum_{i=1}^{n}\max(0,h_i-H).$ 求使木材总量至少为 $M$ 的最大整数 $H$。题目保证 $M$ 不超过所有树的总高度。

输入格式

第一行两个整数 $n$ 和 $M$。第二行 $n$ 个整数 $h_1,h_2,\dots,h_n$。

输出格式

输出一个整数，表示最大的可行锯口高度 $H$。

数据范围与约定

$1 \le n \le 5\times 10^5$，$1 \le M \le \sum h_i$，$1 \le h_i \le 10^9$。

样例输入

4 7
20 15 10 17

样例输出

15

样例说明

当 $H=15$ 时，木材量为 $(20-15)+(17-15)=7$，恰好满足 $M=7$；当 $H=16$ 时只有 $4+1=5$，不满足。因此答案为 $15$。

说明

课程自编题，数据由 src/gen.py 生成。