TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1363
  • 题目
  • P1363【COCI 2011/2012 CONTEST #5-2】砍树
    限制 : 时间限制 : 10000 MS   空间限制 : 32000 KB
    问题描述

    N棵树,每棵都有一个整数高度。有一个木头的总需要量M。

    现在确定一个最大的统一的砍树高度H,如果某棵树的高度大于H,则高出的部分被砍下。使得所有被砍下的木材长度之和达到M(允许稍超过M)。


    例如,有4棵树,高度分别是20 15 10 17, 需要的木材长度为 7,砍树高度为15时,第1棵树被砍下5,第4棵树被砍下2,得到的总长度为7。如果砍树高度为16时,第1棵树被砍下4,第4棵树被砍下1,则得到的木材数量为5。


    输入格式

    第1行:2个整数N和M,N表示树木的数量(1 ≤ N ≤ 1 000 000),M表示需要的木材总长度(1 ≤ M ≤ 2 000 000 000)。


    第2行: N个整数表示每棵树的高度,值均不超过1 000 000 000。所有木材高度之和大于M,因此必然有解。

    输出格式

    第1行:1个整数,表示砍树的最高高度。

    样例输入

    5 20
    4 42 40 26 46

    样例输出

    36


    来源  Croatian Open Competition in Informatics 2011/2012