题目理解

我们有 $N$ 只怪兽，每只怪兽在时刻 $S_i$ 出现，基础生命值 $H_i$，强度 $P_i$。选择难度 $\ell$ 时，实际生命值为 $\ell \times H_i$。

战斗持续 $T$ 秒，每秒可以攻击一只怪兽。最终评价值为 $\sum h_i P_i$，其中 $h_i$ 是剩余生命值。要求对于每个标准值 $M_j$，找到能完成任务的最大难度 $\ell$。

关键观察

1. 问题转化

设难度为 $\ell$，我们需要最小化 $\sum h_i P_i$。这是一个调度问题：如何分配有限的攻击时间来最小化加权剩余生命值。

2. 最优策略

按照出现时间从早到晚处理怪兽，优先攻击强度 $P_i$ 大的怪兽。这可以通过交换论证证明是最优的。

3. 数学建模

对于固定难度 $\ell$，最小评价值可以表示为：

$$\min \sum_{i=1}^N \max(0, \ell H_i - \text{分配给i的攻击次数}) \times P_i $$

算法核心

凸包优化 + 差分数组

代码使用了凸包技巧来高效计算所有难度下的最小评价值。

算法流程

步骤1：预处理和排序

// 按出现时间排序（实际上存储的是剩余时间 T - S_i）
sort(a + 1, a + 1 + n);
// 对强度值离散化
sort(b + 1, b + 1 + n);
tot = unique(b + 1, b + 1 + n) - (b + 1);

步骤2：按强度阈值分组处理

对于每个强度阈值 $b_i$，考虑所有 $P_j \geq b_i$ 的怪兽：

for i = 1 to tot:
    // 构建凸包
    s[t = 1] = 0;
    for j = 1 to n:
        if a[j].p >= b[i]:
            sum += a[j].h;
            d[j] = (line){sum, -a[j].s};  // 斜率=累计生命值，截距=-剩余时间
            // 维护凸包

步骤3：凸包维护

使用单调栈维护下凸壳：

while t > 1 && get(d[s[t-1]], d[s[t]]) >= get(d[s[t]], d[j]))
    t--;
s[++t] = j;

这里 get(a, b) 计算两条直线的交点：

$$\frac{b.b - a.b}{a.k - b.k}$$

步骤4：计算每个难度区间的贡献

对于凸包上的每个线段，计算它在难度区间 $[l, r]$ 内的贡献：

for j = 1 to t:
    l = max(1, 交点坐标)
    r = min(L, 下一个交点坐标)
    c[l] += w * d[s[j]]  // w = b[i] - b[i-1]
    c[r+1] -= w * d[s[j]]

步骤5：前缀和恢复

for i = 1 to L+1:
    c[i] = c[i-1] + c[i]

步骤6：二分查询

对于每个查询 $M_j$，二分查找最大的 $\ell$ 使得：

$$c[\ell].k \times \ell + c[\ell].b \leq M_j$$

算法正确性

1. 凸包优化的原理

最小评价值函数关于难度 $\ell$ 是分段线性的凸函数。通过维护凸包，可以高效计算所有难度下的最小值。

2. 强度分组的意义

按强度阈值分组，利用容斥原理：

• 考虑 $P \geq b_i$ 的怪兽
• 权重 $w = b_i - b_{i-1}$ 实现差分
• 最终通过前缀和恢复完整函数

3. 时间处理技巧

代码中 a[i].s = T - a[i].s，这样 a[i].s 表示从出现到结束的可用时间，便于计算。

时间复杂度

• 排序: $O(N \log N)$
• 凸包构建: $O(N)$ 每个强度组，总 $O(N^2)$
• 查询: $O(Q \log L)$

由于 $N \leq 6000$，$O(N^2)$ 是可接受的。

关键数据结构

1. 怪兽信息: a[N] 存储 $(S_i, H_i, P_i)$
2. 强度离散化: b[N] 存储所有不同的 $P_i$
3. 直线表示: line{k, b} 表示 $y = kx + b$
4. 差分数组: c[M] 存储难度函数的差分

算法优势

1. 凸包优化: 将复杂的最小化问题转化为几何问题
2. 差分技巧: 通过强度分组和差分，避免重复计算
3. 预处理: 所有查询可以在对数时间内回答
4. 数学严谨: 基于凸函数性质，保证正确性

算法标签

• 凸包优化
• 离散化
• 差分数组
• 二分查找
• 贪心策略

总结

该算法通过巧妙的凸包优化和差分技巧，解决了复杂的难度选择问题。核心思想是将最小评价值函数表示为分段线性凸函数，通过维护凸包来高效计算所有难度下的最优值。算法充分利用了问题的数学结构，实现了高效的预处理和查询，是该类优化问题的经典解法。