思路与算法

怪物只有血量小于0才死亡，因此需要累计伤害至少m_i+1。给定火球伤害p，判断能否在不超过k次内全部消灭。伤害随p增加不会减少，可二分最小可行p；上界max(m)+1+(n-1)^2保证向最右怪物射一颗就能杀死所有怪物。

判定从右到左处理。已固定的右侧火球给当前位置造成damage，若damage<=m_i，就在当前位置追加ceil((m_i+1-damage)/p)颗；次数超过k立即返回不可行。新火球放当前位置，对尚未处理的左侧位置最有利。

为避免逐颗影响整段，只保留距离平方小于p的有效火球。队列按射击位置从大到小排列，维护Q=sum q、J=sum(qj)、J2=sum(qjj)。当前位置i的总伤害展开为Qp-J2+2iJ-iiQ。进入更左位置前，弹出距离平方>=p的最右旧火球，扣除对应三个和。每个射击位置最多入队、出队一次，一次判定O(N)。

正确性说明

先证明右到左贪心。假设右侧位置均已由固定火球杀死。当前位置若还欠D>0伤害，每个尚未固定的火球在此处最多贡献p，所以至少还要ceil(D/p)颗。在任何可行方案中，选出这么多能影响当前位置的未固定火球，其位置必不在当前位置左方。把它们移动到当前位置：对任意未处理位置x<=i，新距离i-x不大于旧距离j-x，所以新溅射伤害不低；当前位置获得每颗p的伤害，足够补足。已处理的右侧仍由先前固定火球保证死亡，不依赖这些未固定火球。因此每步都能把任意可行方案改造成贪心前缀且不增加次数。最终贪心使用最少次数，超过k时无可行方案，否则存在可行方案。若要求恰射k颗，额外火球不会减少伤害，故与不超过k等价。

距离平方>=p的火球对当前位置及其左方伤害恒为0，可永久删除；剩余火球的贡献正好是q*(p-(j-i)^2)。展开并求和得到维护公式，故每步damage及所需追加次数准确，判定实现正确。

固定任意射击方案，增大p会使每个怪物受到的伤害不减，所以可行伤害值为一个后缀。上述上界能用一颗火球使最远位置也受到至少max(m)+1伤害，k>=1时必可行。闭区间二分按准确判定保留最小可行值，终止时得到答案。

复杂度

读取N个血量O(N)。每次判定初始化空队列和三个和O(1)，扫描N个位置，每个位置至多入队一次、出队一次，总时间O(N)，空间O(N)。若U=max(m)+1+(N-1)^2，二分O(log U)次，含初始化总时间O(N log U)，额外空间O(N)。p上界约3.5乘10^9，必须用64位；最多保留k次火球，三项加权和及伤害中间量在约10^15量级以内，均适合long long。

易错点

1. 血量恰为0时仍存活，缺口是m_i+1-damage，不是m_i-damage。
2. 火球只向左溅射，不能使用对称覆盖；尸体不改变下标距离。
3. 有效条件是距离平方严格小于p，等于p时伤害为0，应移出队列。
4. p可能大于32位有符号上限，平方、次数乘位置、加权和及二分上界都先提升到long long。
5. 不用浮点开平方决定窗口；用整数平方比较避免边界误差。追加次数用整数向上取整，并在写入加权和之前检查是否超出k。
6. 覆盖单个怪物、最大血量、k=1的大伤害、N与k同时最大、交错血量和低血量零半径附近，独立小规模全火球分配穷举核验。

参考代码（C++11）

#include <algorithm>
#include <deque>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll k;
    cin >> n >> k;
    vector<ll> a(n);
    for (ll &x : a)
        cin >> x;
    auto check = [&](ll p) {
        deque<pair<int, ll>> q;
        ll used = 0, Q = 0, J = 0, J2 = 0;
        for (int i = n - 1; i >= 0; --i) {
            while (!q.empty() && 1LL * (q.front().first - i) * (q.front().first - i) >= p) {
                ll j = q.front().first, c = q.front().second;
                q.pop_front();
                Q -= c;
                J -= c * j;
                J2 -= c * j * j;
            }
            ll damage = Q * p - J2 + 2LL * i * J - 1LL * i * i * Q;
            if (damage <= a[i]) {
                ll count = (a[i] + 1 - damage + p - 1) / p;
                if (count > k - used)
                    return false;
                used += count;
                q.push_back({i, count});
                Q += count;
                J += count * i;
                J2 += count * i * i;
            }
        }
        return true;
    };
    ll lo = 1, hi = *max_element(a.begin(), a.end()) + 1 + 1LL * (n - 1) * (n - 1);
    while (lo < hi) {
        ll mid = lo + (hi - lo) / 2;
        if (check(mid))
            hi = mid;
        else
            lo = mid + 1;
    }
    cout << lo << '\n';
}