题目大意

Bajtazar 经营一个烤三明治摊位，每天有 $k$ 位顾客，第 $i$ 位在时刻 $t_i$ 到达。烤箱一次最多烤 $z$ 份三明治，每批耗时 $d$ 时间。三明治必须在顾客到达时刚好烤好（不能提前太多变凉，也不能让顾客等待）。

Bajtazar 在时刻 $0$ 到达摊位，已知所有顾客到达时间，求采用最优烤制策略时，顾客的总等待时间的最小值。

解题思路

问题分析

这是一个典型的调度优化问题，具有以下特点：

1. 顺序决策：需要决定何时启动烤箱、每次烤多少份
2. 容量限制：一次最多烤 $z$ 份
3. 时间约束：必须在顾客到达时刻烤好
4. 目标优化：最小化总等待时间

动态规划解法

设 dp[i] 表示处理完前 i 个顾客的最小总等待时间。

状态转移

对于每个 i（1 ≤ i ≤ k），我们枚举最后一批烤制的顾客范围 [j+1, i]，其中 max(0, i-z) ≤ j < i。

对于每个可能的 j：

• 最后一批处理顾客 j+1 到 i，共 batch_size = i - j 份
• 这批的开始时间必须满足：
  1. 在前一批结束后（如果 j > 0）
  2. 保证所有顾客到达时三明治已烤好

开始时间计算

开始时间 start_time 需要满足：

• start_time + d ≥ t[customer] 对于所有 customer ∈ [j+1, i]
• 如果 j > 0，则 start_time ≥ dp[j] + d（前一批结束时间）

因此：

start_time = max({t[customer] - d for customer in [j+1, i]})
if j > 0:
    start_time = max(start_time, dp[j] + d)

等待时间计算

对于顾客 customer ∈ [j+1, i]：

finish_time = start_time + d
wait_time = max(0, finish_time - t[customer])

总等待时间就是这些等待时间的和。

算法优化

直接实现的时间复杂度是 $O(k^2z)$，对于 $k \leq 3000$ 可能较慢。可以优化：

1. 预处理：计算每个区间 [j+1, i] 的最大 t[customer] - d
2. 单调性利用：开始时间具有单调性，可以减少计算
3. 提前终止：某些状态明显不优时可以提前跳过

代码实现

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

int main() {
    int k, z, d;
    cin >> k >> z >> d;
    
    vector<int> t(k + 1);
    for (int i = 1; i <= k; i++) {
        cin >> t[i];
    }
    
    // dp[i] 表示处理完前i个顾客的最小总等待时间
    vector<long long> dp(k + 1, LLONG_MAX);
    dp[0] = 0;
    
    // 预处理max_t[i][j] = max{t[i]-d, t[i+1]-d, ..., t[j]-d}
    vector<vector<int>> max_t(k + 1, vector<int>(k + 1));
    for (int i = 1; i <= k; i++) {
        max_t[i][i] = t[i] - d;
        for (int j = i + 1; j <= k; j++) {
            max_t[i][j] = max(max_t[i][j - 1], t[j] - d);
        }
    }
    
    for (int i = 1; i <= k; i++) {
        // 枚举最后一批的起始位置
        for (int j = max(0, i - z); j < i; j++) {
            int batch_size = i - j;
            
            // 计算这批的开始时间
            long long start_time;
            if (j == 0) {
                start_time = max(0, max_t[j + 1][i]);
            } else {
                start_time = max((long long)dp[j] + d, (long long)max_t[j + 1][i]);
            }
            
            // 计算总等待时间
            long long wait_time = 0;
            for (int customer = j + 1; customer <= i; customer++) {
                long long finish_time = start_time + d;
                wait_time += max(0LL, finish_time - t[customer]);
            }
            
            // 更新DP值
            if (dp[j] != LLONG_MAX) {
                dp[i] = min(dp[i], dp[j] + wait_time);
            }
        }
    }
    
    cout << dp[k] << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度：$O(k^2z)$，最坏情况下 $O(k^3)$
• 空间复杂度：$O(k^2)$

优化思路

对于更大规模的数据，可以考虑以下优化：

1. 状态压缩：利用滚动数组减少空间复杂度
2. 决策单调性：利用开始时间的单调性优化枚举
3. 数据结构优化：使用线段树等快速查询区间最大值
4. 贪心启发：结合贪心策略减少状态枚举

总结

本题是一个典型的动态规划调度问题，关键在于：

• 合理定义状态：dp[i] 表示前 i 个顾客的最小等待时间
• 正确处理时间约束：必须在顾客到达时烤好
• 考虑烤箱容量限制：每批最多烤 z 份

通过枚举最后一批的烤制方案，我们可以找到最优的调度策略，最小化顾客的总等待时间。