这道CSP41-B《机器人项目管理》的核心其实非常清晰普通型任务 0/1 背包灵活型任务 可以任意切分咖啡因此按“单位咖啡收益”贪心。但真正的难点在于这两种任务混在一起时怎么组合一、先把题目翻译成数学问题有n个任务。第i个任务o[i]任务类型 t[i]原始耗时 a[i]最多能喝多少杯咖啡 b[i]喝满 a[i] 杯后最多缩短多少时间初始总时间T∑ti我们有最多m杯咖啡。目标是让总时间尽可能小。等价于让总减少时间尽可能大。所以问题可以转化为m 杯咖啡 ↓ 如何分配 ↓ 获得最大的“时间减少量”最后答案∑ti−最大减少时间答案\sum t_i-最大减少时间题目中灵活型和普通型的规则分别如下。二、灵活型任务是什么假设a 5 b 10喝满5 杯咖啡减少10 时间那么灵活型可以喝任意实数杯。例如咖啡减少时间00122.5548510因为它是线性的。如果给x杯咖啡减少时间bi / ai *x所以每杯咖啡的收益是bi / ai这个值非常重要。三、灵活型任务应该怎么分配假设有三个任务任务 1a 2b 10任务 2a 4b 12任务 3a 5b 10每杯咖啡收益任务 110 / 2 5任务 212 / 4 3任务 310 / 5 2那么应该先给任务 1 再给任务 2 最后给任务 3也就是说灵活型任务按照 bi / ai从大到小贪心。四、普通型任务有什么不同普通型任务只能不喝 或者一次喝满 a[i] 杯例如a 5 b 10只能选择0 杯 → 减少 0或者5 杯 → 减少 10不能3 杯 → 减少 6所以普通型任务就是重量 a[i] 价值 b[i] 的一个物品。这就是标准的0/1 背包设dp[j]表示 使用j杯咖啡普通型任务最多能减少多少时间。转移for (int j m; j a[i]; j--) { dp[j] max(dp[j], dp[j - a[i]] b[i]); }注意一定要从大到小因为每个普通型任务只能选一次。五、混合情况才是真正的核心假设我们先决定普通型任务用了 j 杯咖啡那么剩余咖啡 m - j剩下的全部给灵活型任务。因此总减少时间 普通型任务减少时间 灵活型任务减少时间也就是dp[j]flex(m−j)其中dp[j]表示用普通型任务消耗j杯咖啡最大减少时间。而flex(x)表示用x杯咖啡给灵活型任务最大能减少多少时间。最后枚举for (int j 0; j m; j) { ans max(ans, dp[j] flex(m - j)); }六、灵活型的flex(x)怎么计算假设灵活任务是任务ab单位收益A2105B393C482排序后A → B → C也就是每杯减少时间 5 3 2假设x 4 杯咖啡先给 AA 最多需要 2 杯 减少 10还剩2 杯给 B每杯减少 3所以总共10 6 16因此flex(4)16七、如何高效计算所有flex(x)因为m 1000 n 200其实直接计算都不会太慢。但我们可以先排序struct Task { int a, b; }; sort(flex.begin(), flex.end(), [](Task x, Task y) { return 1.0 * x.b / x.a 1.0 * y.b / y.a; });不过这里有精度问题。更好的比较方式是b1/a1b2/a2等价于b1*a2b2*a1所以sort(flex.begin(), flex.end(), [](Task x, Task y) { return 1LL * x.b * y.a 1LL * y.b * x.a; });然后计算double calc(int coffee) { double res 0; for (auto [a, b] : flex) { int use min(coffee, a); res 1.0 * use * b / a; coffee - use; if (coffee 0) break; } return res; }这里为什么use是整数也没关系因为我们最终计算的是普通任务用了 j 杯其中j是整数。剩下m - j也是整数。虽然灵活型允许实数杯咖啡但对于固定的总咖啡量x把前面的任务喝满 最后一个任务喝 x - 前面使用量这里前面使用的都是整数a[i]所以剩下仍然是整数。因此我们只需要计算flex(0) flex(1) ... flex(m)八、完整算法现在整个算法就出来了。第一步计算原始总时间double total 0; for (...) { total t[i]; }第二步普通任务做 0/1 背包vectordouble dp(m 1, 0);对于每个普通任务for (int j m; j a; j--) { dp[j] max(dp[j], dp[j - a] b); }第三步灵活任务排序按照bi / ai从大到小排序。第四步计算flex[x]for (int x 0; x m; x) { int coffee x; for (auto task : flex) { int use min(coffee, task.a); f[x] 1.0 * use * task.b / task.a; coffee - use; if (coffee 0) break; } }第五步枚举普通任务使用多少咖啡double best 0; for (int j 0; j m; j) { best max(best, dp[j] f[m - j]); }最终cout fixed setprecision(10) total - best;题目的范围是n ≤ 200, m ≤ 1000最终代码如下#include bits/stdc.h using namespace std; using ll long long; struct Task { int a, b; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; double totalTime 0; vectorTask flexible; // dp[j] // 使用普通型任务恰好/至多消耗 j 杯咖啡时 // 能获得的最大时间减少量 vectordouble dp(m 1, 0); for (int i 0; i n; i) { int o, t, a, b; cin o t a b; totalTime t; if (o 0) { // 灵活型 flexible.push_back({a, b}); } else { // 普通型0/1 背包 for (int j m; j a; j--) { dp[j] max(dp[j], dp[j - a] b); } } } // 按单位咖啡收益 b / a 从大到小排序 sort(flexible.begin(), flexible.end(), [](const Task x, const Task y) { return 1LL * x.b * y.a 1LL * y.b * x.a; }); // flex[i]i 杯咖啡全部给灵活型任务 // 最多减少多少时间 vectordouble flex(m 1, 0); for (int coffee 0; coffee m; coffee) { int remain coffee; double reduce 0; for (auto task : flexible) { int use min(remain, task.a); reduce 1.0 * use * task.b / task.a; remain - use; if (remain 0) break; } flex[coffee] reduce; } // 枚举 // j 杯给普通型任务 // m-j 杯给灵活型任务 double bestReduce 0; for (int j 0; j m; j) { bestReduce max(bestReduce, dp[j] flex[m - j]); } double answer totalTime - bestReduce; cout fixed setprecision(10) answer \n; return 0; }