第41次ccfcsp机器人项目管理

题目：
小 P 计划招募 n 个机器人完成一个项目：每个机器人负责其中的一项任务，编号从 1 到 n，任务之间互不干扰。如果完成任务 i 的耗时为 ti​，则该项目总耗时为 t1+t2+⋯+tn。

作为项目管理者，小 P 可以用有限的预算为机器人们购买咖啡加油。其中负责任务 i 的机器人，最多可以喝 ai 杯咖啡，从而将该任务耗时缩短 bi​（最终耗时即为 ti−bi​）。

根据任务的特性和机器人的偏好，n 项任务可分为“灵活型”和“普通型”两类。

灵活型：如果任务 i 是灵活型，则可以提供给该任务 [0,ai​] 范围内的任意实数杯咖啡，从而将其加速相应比例。

若给任务 i 提供 ki​⋅ai​ 杯咖啡，则该任务对应耗时 ti​−ki​⋅bi​ (0≤ki​≤1)。

普通型：只能提供给任务 0 或 ai​ 杯咖啡。

换言之，只有将耗时缩短 bi 和不加速两种选择，而不能提供半杯咖啡。

已知小 P 可以为机器人们提供最多 m 杯咖啡，试计算完成整个项目的最短时间。

输入格式

从标准输入读入数据。

输入的第一行包含空格分隔的两个正整数 n 和 m，分别表示任务数量和咖啡数量。

接下来 n 行，每行包含空格分隔的四个整数 oi,ti,ai,bi​，表示一个任务。其中 oi∈{0,1} 表示任务类别，oi​=0 表示灵活型、oi​=1 表示普通型；其余变量含义如上所述，输入数据保证 ti​>bi​，即缩短后的耗时仍大于零。

输出格式

输出到标准输出。

输出一个实数，表示完成整个项目的最短时间。

这个代码用的贪心逻辑，完全没有用二分：

这只是我想出来的一个解法，但是可能有其他没有考虑全面的地方，如果用问题可以提出。

#include <bits/stdc++.h> using namespace std; // 定义全局数组，分别存储任务类型(o)、原始耗时(t)、最多分配咖啡数(a)、最多减少时长(b) int o[1000]={0}, t[1000]={0}, a[1000]={0}, b[1000]={0}, ans=0; int main(){ int n, m; // 输入任务总数 n 和 咖啡总数 m cin >> n >> m; // 定义索引数组 g，用于后续排序（记录任务的下标） int g[n]={0}; // e 数组存储每个任务的“性价比”（每杯咖啡能减少的时间），sum 记录所有任务的原始总耗时 double e[1000]={0}, dp[1000]={0}, sum=0, ans=0; // 1. 读取输入并预处理 for(int i=1; i<=n; i++){ // 按照题目要求输入：类型、时间、倍数、减少时间 cin >> o[i] >> t[i] >> a[i] >> b[i]; // 计算性价比：总减少时长 / 总杯数 e[i] = 1.000 * b[i] / a[i]; // 累加原始总耗时 sum = sum + t[i]; } // 初始化索引数组，g[i] 存储任务的原始下标 i for(int i=1; i<=n; i++){ g[i] = i; } // 2. 贪心核心：按性价比从高到低对任务下标进行排序 sort(g+1, g+n+1, [&](int f, int h){ return e[f] > e[h]; // 性价比高的任务排在前面，优先分配咖啡 }); // 3. 遍历排序后的任务，依次分配咖啡 for(int i=1; i<=n; i++){ // 如果是固定型任务(o==1)，且剩下的咖啡足够满足它的最大需求 if(o[g[i]] == 1 && a[g[i]] <= m){ ans = ans + b[g[i]]; // 直接加上它能减少的最大时长 m = m - a[g[i]]; // 扣除消耗的咖啡 } // 如果是灵活型任务(o==0)，且手里还有剩余咖啡 else if(o[g[i]] == 0 && m > 0){ // 情况A：剩下的咖啡足够把这个灵活型任务喝满 if(m >= a[g[i]]) { ans = ans + b[g[i]]; // 加上最大减少时长 m = m - a[g[i]]; // 扣除消耗的咖啡 } // 情况B：剩下的咖啡不够喝满，只能全部给它（此时可以喝小数杯） else { // 减少的时长 = 剩余咖啡数 * 每杯的性价比 ans = ans + m * e[g[i]]; m = 0; // 咖啡全部用完 } } } // 4. 输出最终结果：原始总耗时 - 通过喝咖啡减少的总时长 cout << sum - ans; return 0; }