#P7010. 砍树
砍树
Description
在一片树林里, 有 N 颗树,你需要砍下 M 米的木头.
仅有一排树木可以供你砍伐
伐木机的工作原理如下:设置高度参数 H(以米为单位),机器将一个巨大的锯片提升到那个高度,并切断高于 H 的所有树木部分(当然,不高于 H 米的树木仍然完好无损).
例如:
如果有一排树木高度为 20,15,10 和 17 米,参数设为 15 米,
切割后剩余的树的 高度将是 15,15,10 和 15 米,得到的木头为第一棵树的 5 米和第四棵树的 2 米,总共 7 米。
因为提倡生态意识,所以不能砍下不必要的木头。
这就是为什么要把锯条尽可能地抬高。
请你找到最大的整数高度的锯片,使得你砍下至少 M 米的木头..
Format
Input
第一行包含两个空格分隔的正整数,N(1≤N≤1 000 000),M(1≤M≤2 000 000 000),含 义见题面.
第二行输入包含 N 个空格分隔的小于 1000000 的正整数.
第 i 个正整数表示第 i 棵的 高度.
保证所有树的高度和大于 M..
Output
一行一个正整数 H,即可以获得 M 米木材的前提下,设置锯片的最大高度
Samples
输入数据1
4 7
20 15 10 17
输出数据1
15
Limitation
250ms, 1024KiB for each test case.
统计
相关
在下列比赛中: