信息学奥赛一本通(C++版)在线评测系统

本网站由成都石室中学、福建长乐一中信奥教练联合呈现。题库教师群:307432527,仅供教师加入
围观:初赛那点事!
提高 普及
你现在还未登录哦!
用户登录
注册新用户

1676:手机游戏


时间限制: 1000 ms         内存限制: 131072 KB
提交数: 593     通过数: 182

【题目描述】

明明的手机上有这样一个游戏,一排$n$个怪物,每个怪物的血量是$m_i$。现在明明可以射出$k$个伤害均为$p$的火球,当某个火球射到第$i$个怪物,除了这个怪物会掉血$p$以外,它左边的第$j$个怪物($j≤i$),也会遭到$max(0,p-(i-j)^2)$的溅射伤害。当某个怪物的血量为负的时候,它就死了,但它的尸体依然存在,即其他怪物不会因为它死而改变位置。

明明想用这$k$个火球消灭掉所有的怪物,但他同时希望每个火球的伤害$p$能尽可能的小,这样他才能完美过关。

所有数均为整数。

【输入】

第一行两个数$n,k$。

第二行$n$个数$m_1,m_2,…,m_n$表示每个怪物的生命值。

【输出】

一行一个整数表示最小的符合要求的$p$值。

【输入样例】

3 1
1 4 5

【输出样例】

6

【提示】

【数据规模】

对于30%的数据,$n≤500$。

对于100%的数据,$1≤n≤50000,1≤k≤100000,1≤m_i≤10^9$。

提交 统计信息


本题库与《信息学奥赛一本通(C++版)》(科学技术文献出版社)配套,版权及相关事宜请与本书作者联系,本网站不作解答。
本网站属公益、非盈利性质,不涉及与书相关的商业活动,后期可能适当收取费用以支持网站的运行维护。
目前因个人编写水平有限,网站维护、网站安全方面及部分功能的开发尚不成熟,如遇疑问,请通过版主信箱联系。
感谢成都石室中学Wuvin、Qizy、Xehoth三位同学对本网站的支持,特别鸣谢北京师范大学ACM前校队易超、唐巧、洪涛同学。
版主信箱:ybt_mail@126.com