Tom's Kitchen 题解

题目分析

这道题来自 BalticOI 2019 Day2 T1，是一个组合优化问题。题目要求我们找到最优的雇佣厨师方案，使得厨师不工作就获得报酬的小时数最小。

关键约束条件

1. 每道菜必须由至少 K 名厨师准备
2. 每名厨师准备菜品时必须花费正整数小时
3. 厨师即使工作时间不足上限，也会按上限获得报酬
4. 每道菜的总准备时间恰好等于其所需时间

解题思路

可行性判断

首先需要判断是否存在可行解：

• 如果厨师总数 m < k，无法满足每道菜至少需要 k 名厨师的要求
• 如果某道菜的准备时间 A_i < k，无法满足每名厨师都花费正整数小时的要求

核心算法

代码使用了动态规划来解决这个问题：

1. 状态定义：f[j] 表示总工作时间为 j 时，能够覆盖的最大"厨师-菜品"对数
2. 状态转移：对于每个厨师的工作时间上限 a[i]，进行背包式的状态更新
3. 关键观察：每个厨师最多只能参与 n 道菜的准备工作（因为有 n 道菜）

算法流程

1. 读入输入数据
2. 检查可行性条件
3. 使用动态规划计算所有可能的工作时间分配方案
4. 寻找满足条件的最小总工作时间
5. 输出结果（最小额外支付时间或 "Impossible"）

代码详解

#include <bits/stdc++.h>
using namespace std;

const int N = 305;
int n, m, k, a[N], b[N];
int f[N * N];  // 动态规划数组

int main() {
    // 读入数据
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) cin >> b[i];  // 菜品准备时间
    for (int i = 1; i <= m; i++) cin >> a[i];  // 厨师工作时间上限
    
    // 可行性检查
    if (m < k || *min_element(b + 1, b + n + 1) < k)
        return puts("Impossible"), 0;
    
    int sum = accumulate(a + 1, a + m + 1, 0);  // 所有厨师总工作时间上限
    memset(f, 0xcf, sizeof f);  // 初始化为负无穷
    f[0] = 0;  // 初始状态
    
    // 动态规划 - 背包思想
    for (int i = 1; i <= m; i++) {
        int v = min(n, a[i]);  // 该厨师最多能参与的菜品数
        for (int j = sum; j >= a[i]; j--)
            f[j] = max(f[j], f[j - a[i]] + v);
    }
    
    int s = accumulate(b + 1, b + n + 1, 0);  // 所有菜品总准备时间
    
    // 寻找最优解
    for (int i = s; i <= sum; i++)
        if (f[i] >= n * k)  // 检查是否满足每道菜至少k名厨师
            return printf("%d\n", i - s), 0;
    
    puts("Impossible");
    return 0;
}

样例分析

样例1

输入: 1 2 2
       5
       3 4
输出: 2

• 需要雇佣2名厨师（因为k=2）
• 菜品准备时间：5小时
• 厨师工作时间上限：3+4=7小时
• 额外支付：7-5=2小时

样例2

输入: 1 1 2
       5
       5
输出: Impossible

• 需要至少2名厨师，但只有1名可用

样例3

输入: 3 3 3
       3 3 2
       3 3 3
输出: Impossible

• 第三道菜准备时间只有2小时，但需要3名厨师，无法满足每名厨师都工作正整数小时

复杂度分析

• 时间复杂度：O(M × Σa[i])，其中 M 是厨师数量
• 空间复杂度：O(Σa[i])，使用一维动态规划数组

总结

这道题的关键在于将问题转化为动态规划模型，通过计算不同总工作时间下能够覆盖的最大"厨师-菜品"对数，来找到满足条件的最优解。算法巧妙地利用了背包问题的思想，同时考虑了题目特有的约束条件。