题目小 P 计划招募 n 个机器人完成一个项目每个机器人负责其中的一项任务编号从 1 到 n任务之间互不干扰。如果完成任务 i 的耗时为 ti则该项目总耗时为 t1t2⋯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} 表示任务类别oi0 表示灵活型、oi1 表示普通型其余变量含义如上所述输入数据保证 tibi即缩短后的耗时仍大于零。输出格式输出到标准输出。输出一个实数表示完成整个项目的最短时间。这个代码用的贪心逻辑完全没有用二分这只是我想出来的一个解法但是可能有其他没有考虑全面的地方如果用问题可以提出。#include bits/stdc.h using namespace std; // 定义全局数组分别存储任务类型(o)、原始耗时(t)、最多分配咖啡数(a)、最多减少时长(b) int o[1000]{0}, t[1000]{0}, a[1000]{0}, b[1000]{0}, ans0; int main(){ int n, m; // 输入任务总数 n 和 咖啡总数 m cin n m; // 定义索引数组 g用于后续排序记录任务的下标 int g[n]{0}; // e 数组存储每个任务的“性价比”每杯咖啡能减少的时间sum 记录所有任务的原始总耗时 double e[1000]{0}, dp[1000]{0}, sum0, ans0; // 1. 读取输入并预处理 for(int i1; in; 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 i1; in; i){ g[i] i; } // 2. 贪心核心按性价比从高到低对任务下标进行排序 sort(g1, gn1, [](int f, int h){ return e[f] e[h]; // 性价比高的任务排在前面优先分配咖啡 }); // 3. 遍历排序后的任务依次分配咖啡 for(int i1; in; i){ // 如果是固定型任务(o1)且剩下的咖啡足够满足它的最大需求 if(o[g[i]] 1 a[g[i]] m){ ans ans b[g[i]]; // 直接加上它能减少的最大时长 m m - a[g[i]]; // 扣除消耗的咖啡 } // 如果是灵活型任务(o0)且手里还有剩余咖啡 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; }
