P1485 火枪打怪

    • 229通过
    • 1.2K提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 二分答案 线性结构 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    LXL进入到了一片丛林,结果他发现有n只怪物排成一排站在他面前。LXL有一杆火枪能对付这些怪物。他知道从左至右数第i只怪物的血量是mi。现在LXL可以将一些子弹射向某个怪物。LXL可以控制他所发射的子弹数量及子弹的威力值。当某个子弹射到第i个怪物,如果这个子弹的威力值为p,除了这个怪物会掉p点血以外,它左边的第j个怪物(j<i),也会遭到Max(0, p - (i - j) * (i - j))的溅射伤害(好神奇的子弹)。当某只怪物的血量小于0时,它就死了,但它的尸体还在,即怪物的位置永远不会改变。LXL希望只用k发子弹,请你求出一个最小的正整数p,使LXL用k发子弹且每发子弹的威力值为p就可以消灭所有怪物。

    输入输出格式

    输入格式:

    第一行,两个正整数n,k。

    第二行,n个正整数,第i个正整数表示从左至右数第i只怪物的血量mi。

    输出格式:

    一个正整数,表示子弹的最小威力值p。

    输入输出样例

    输入样例#1: 复制
    3 1
    1 4 5
    
    输出样例#1: 复制
    6

    说明

    对于30%的数据,n<=300。

    对于100%的数据,n<=500000,k<=500000,1<=mi<=10^10

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。