各位好，今天我们来看CSP202603B. 机器人项目管理这道题目

题目简述

有 n 个任务，完成所有任务的基础总耗时为所有 ti 之和。现有 m 杯咖啡可供分配，每个任务喝咖啡后可缩短耗时：

• 灵活型任务：可喝任意实数杯咖啡（0 到 ai），缩短耗时与杯数成正比，每杯效率为 bi/ai

• 普通型任务：只能选择喝 ai 杯（缩短 bi）或不喝（不缩短）

求合理分配咖啡后，完成所有任务的最短总耗时。

猜想

能否直接通过每杯咖啡缩短尽可能多的时间贪心，来获得全局最优解呢？

如果全是灵活型任务，答案是肯定的。灵活型任务可以连续取值，每多给一杯咖啡就多节省 时间，不存在"浪费"，所以按效率从高到低依次分配就是最优解，这是经典的分数背包问题。

但对于普通型任务，情况完全不同，我们假设有两个普通型任务：

• 任务A：需要 3 杯咖啡，节省 5 小时（效率 1.67）

• 任务B：需要 4 杯咖啡，节省 6 小时（效率 1.5）

你有 4 杯咖啡。

我们发现此时将4杯咖啡都选给效率略低的任务B才是更优的，也就是说我们不能通过贪心获得全局最优解，考虑DP

为什么需要DP

普通型只能整杯整杯取，不能拆分，这和01背包问题：每个物品要么全拿，要么不拿的情形是一样的，所以对待普通型，我们需要使用01背包获得最优解

于是整体策略变成：

1. 普通型任务：用 DP 求出"消耗 k 杯咖啡，最多能节省多少时间"

2. 灵活型任务：用贪心分配剩余咖啡

3. 枚举分割点：尝试所有可能的 k，取总耗时最小值 

把普通型任务看作 0-1 背包物品：

• 物品重量 = 需要的咖啡杯数

• 物品价值 = 节省的时间

• 背包容量 = 普通型任务所需咖啡总量和 m 的较小值

状态转移方程：

dp[j] = max(dp[j], dp[j - a_i] + b_i)

表示：消耗 j 杯咖啡时，普通型任务最多能节省 dp[j] 的时间。

枚举分给普通型的咖啡数 k（0 到背包容量）：

普通型节省 = dp[k]
剩余咖啡 = m - k
灵活型节省 = 剩余咖啡按效率从高到低贪心分配
总耗时 = 基础总耗时 - 普通型节省 - 灵活型节省

具体细节看下面的参考代码：

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

struct Task {
    int type;        // 0: 灵活型, 1: 普通型
    double t;        // 原始耗时
    double a;        // 所需咖啡杯数
    double b;        // 可缩短的时间
    double efficiency; // 效率 b/a (灵活型使用)
};

int main() {
    int n;
    double m;
    cin >> n >> m;
    
    vector<Task> flexible_tasks;  // 灵活型任务
    vector<Task> normal_tasks;    // 普通型任务
    double base_time = 0;         // 基础总耗时（不加速）
    
    for (int i = 0; i < n; i++) {
        int o;
        double t, a, b;
        cin >> o >> t >> a >> b;
        base_time += t;
        
        if (o == 0) {
            // 灵活型任务
            flexible_tasks.push_back({o, t, a, b, b / a});
        } else {
            // 普通型任务
            normal_tasks.push_back({o, t, a, b, 0});
        }
    }
    
    // 灵活型任务按效率降序排序（贪心准备）
    sort(flexible_tasks.begin(), flexible_tasks.end(), 
         [](const Task& x, const Task& y) {
             return x.efficiency > y.efficiency;
         });
    
    // 普通型任务：计算所需咖啡总量，DP 背包容量
    int max_normal_coffee = 0;
    for (auto& task : normal_tasks) {
        max_normal_coffee += (int)task.a;
    }
    max_normal_coffee = min(max_normal_coffee, (int)m);
    
    // 0-1 背包 DP
    // dp[j] 表示消耗 j 杯咖啡时，普通型任务最多节省的时间
    vector<double> dp(max_normal_coffee + 1, 0);
    
    for (auto& task : normal_tasks) {
        int weight = (int)task.a;
        double value = task.b;
        for (int j = max_normal_coffee; j >= weight; j--) {
            dp[j] = max(dp[j], dp[j - weight] + value);
        }
    }
    
    double ans = base_time;
    
    // 枚举分配给普通型任务的咖啡数量
    for (int normal_coffee = 0; normal_coffee <= max_normal_coffee; normal_coffee++) {
        double remaining_coffee = m - normal_coffee;
        if (remaining_coffee < 0) continue;
        
        double time_saved = dp[normal_coffee];  // 普通型节省的时间
        
        // 灵活型任务用剩余咖啡贪心分配
        double flex_coffee = remaining_coffee;
        for (auto& task : flexible_tasks) {
            if (flex_coffee <= 0) break;
            double use = min(flex_coffee, task.a);
            time_saved += use * task.efficiency;
            flex_coffee -= use;
        }
        
        ans = min(ans, base_time - time_saved);
    }
    
    cout << fixed << setprecision(10) << ans << endl;
    
    return 0;
}

感谢阅读，欢迎在评论区讨论

转载注明出处