题解：任务分组最小费用问题

算法思路

本题是一个经典的任务分批问题，需要将任务序列分成若干批处理，最小化总费用。采用动态规划 + 斜率优化的方法高效求解。

1. 问题分析

设：

• $T_i$：任务 $i$ 的处理时间
• $C_i$：任务 $i$ 的费用系数
• $s$：每批任务的启动时间

费用计算：

• 如果任务 $i$ 到 $j$ 在同一批，它们的完成时间相同
• 完成时间 = 启动时间 + 该批所有任务处理时间之和
• 每个任务的费用 = 完成时间 × 费用系数

2. 动态规划模型

令：

• $sumT_i = \sum_{k=1}^i T_k$：时间前缀和
• $sumC_i = \sum_{k=1}^i C_k$：费用系数前缀和
• $f_i$：处理前 $i$ 个任务的最小费用

状态转移方程：

$$f_i = \min_{0 \le j < i} \{ f_j + sumT_i \times (sumC_i - sumC_j) + s \times (sumC_n - sumC_j) \} $$

3. 斜率优化

将转移方程整理为：

$$f_i = \min_{0 \le j < i} \{ f_j - (s + sumT_i) \times sumC_j \} + sumT_i \times sumC_i + s \times sumC_n $$

设：

• $X_j = sumC_j$
• $Y_j = f_j$
• $K_i = s + sumT_i$

则问题转化为：

$$f_i = \min_{0 \le j < i} \{ Y_j - K_i \times X_j \} + constant $$

这是一个典型的斜率优化问题，可以用凸包维护。

代码实现

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 3e5 + 5;
const LL INF64 = 1LL << 60;

int n, s;
int t[N], c[N];
LL f[N];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> n >> s;
    for (int i = 1; i <= n; i++) {
        cin >> t[i] >> c[i];
        t[i] += t[i-1];  // 时间前缀和
        c[i] += c[i-1];  // 费用系数前缀和
    }
    
    fill(f, f + n + 1, INF64);
    f[0] = 0;
    
    static int q[N];  // 单调队列（存储决策点）
    int top = 0;      // 队列指针
    
    for (int i = 1; i <= n; i++) {
        // 二分查找最优决策点
        auto check = [&](int a, int b) {
            return f[b] - f[a] > 1LL * (s + t[i]) * (c[b] - c[a]);
        };
        
        int l = 0, r = top - 1, j = q[top];
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(q[mid], q[mid + 1])) {
                j = q[mid];
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        
        // 状态转移
        f[i] = f[j] + 1LL * t[i] * (c[i] - c[j]) + 1LL * s * (c[n] - c[j]);
        
        // 维护凸包（删除不在下凸壳上的点）
        while (top > 0) {
            int a = q[top - 1], b = q[top];
            // 检查斜率单调性
            if (1LL * (f[b] - f[a]) * (c[i] - c[b]) >= 
                1LL * (f[i] - f[b]) * (c[b] - c[a])) {
                top--;
            } else {
                break;
            }
        }
        
        q[++top] = i;  // 将当前点加入队列
    }
    
    cout << f[n] << endl;
    return 0;
}

关键优化

1. 斜率优化原理

对于决策点 $j$ 和 $k$（$j < k$），如果：

$$\frac{f_k - f_j}{c_k - c_j} \le s + t_i$$

则 $k$ 比 $j$ 更优。通过维护一个下凸壳，可以快速找到最优决策点。

2. 凸包维护

• 使用单调队列维护候选决策点
• 新加入点时要删除破坏凸性的点
• 查询时在凸包上二分查找切点

3. 二分查找优化

由于斜率 $K_i = s + t_i$ 单调递增，决策点也单调前进，可以用二分快速定位。

复杂度分析

• 时间复杂度：$O(n \log n)$
  • 每个点入队出队一次：$O(n)$
  • 每次二分查找：$O(\log n)$
• 空间复杂度：$O(n)$

对于 $n \leq 3 \times 10^5$ 的数据规模，该算法能够高效运行。

算法正确性

1. 动态规划正确性：状态转移方程完整考虑了所有可能的分组方案
2. 斜率优化正确性：利用凸包性质保证找到全局最优解
3. 数值稳定性：使用 long long 防止整数溢出

这种动态规划 + 斜率优化的方法是处理此类分批问题的最优解法，广泛应用于生产调度、资源分配等领域。