题目链接
1676：手机游戏

时间限制: 1000 ms 内存限制: 131072 KB

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

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

所有数均为整数。

【输入】
第一行两个数n,k。

第二行n个数m1,m2,…,mn表示每个怪物的生命值。

【输出】
一行一个整数表示最小的符合要求的p值。

【输入样例】
3 1
1 4 5
【输出样例】
6
【提示】
【数据规模】

对于30%的数据，n≤500。

对于100%的数据，1≤n≤50000，1≤k≤100000，1≤mi≤10^9。

思路

考虑2分答案
因为只对左边有溅射伤害，所以从右边开始遍历
特别注意：当某个怪物的血量为负的时候，它就死了（血量为0时怪物还活着）

参考代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define pass puts("pass")
#define LL long long
#define N 50004
#define M INT_MAX
using namespace std;

int n,k,ans;
int a[N],b[N];

bool work(int p) {
    int all=k;
    for(int i=1; i<=n; i++) b[i]=a[i];
    for(int i=n; i>=1&&all!=-1; i--)
        while(b[i]>=0&&all!=-1) {
            for(int j=i; j>=1&&(i-j)*(i-j)<p; j--)
                b[j]-=p-(i-j)*(i-j);
            all--;
        }

    //cout<<p<<" "<<all<<"\n";
    if(all==-1) return 0;
    return 1;
}

int main() {
    cin>>n>>k;
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    int l=1,r=M;
    while(l<=r) {
        int mid=(l+r)/2;
        if(work(mid)) {
            ans=mid;
            r=mid-1;
        } else
            l=mid+1;
    }
    cout<<ans<<endl;
    return 0;
}