P1485 火枪打怪

题目描述

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

1
2
3

3 1

1 4 5

输出 #1

说明/提示

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

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

题解

二分答案$p$

接下来用$O(n)$的时间判断$p$是否可行。

~~可以模拟退火找出一组最优解~~

注意到只能向左传递伤害，所以从右往左开火，如果到当前点假设剩余大于$p$，就不可能打死了。

右边第一个必须打，因为左边不可能打死它，然后我们对左边$\sqrt{p}$的范围进行一个区间剪掉等差数列（可能这也是本题唯一难点了)，然后看看右边第二个死了没，没死再开枪再减掉，这是必要的，必定不存在更优的方案。因此贪心是正确的。

所以一个剪掉等差数列的区间线段树不想写了。不过我觉得暴力也差不多能过。