Gone Fishing 贪心 优先队列

Gone Fishing题目描述John 要去钓鱼。他有h 小时的时间1 ≤ h ≤ 16并且该区域有n 个湖泊2 ≤ n ≤ 25这些湖泊通过一条单向道路依次连接。John 从第 1 个湖出发但可以在任意一个湖结束。他只能从湖 i 前往湖 i1但可以选择是否在某个湖停留。对于每个 i 1,…,n-1从湖 i 到湖 i1 需要ti 个 5 分钟单位0 ti ≤ 192。例如t3 4 表示从湖 3 到湖 4 需要 20 分钟。为了规划行程John 收集了以下信息对每个湖 i初始 5 分钟内预计能钓到的鱼数为fifi ≥ 0每经过一个 5 分钟下一时间段的鱼数会减少didi ≥ 0规则说明如果某一时间段预计能钓的鱼数 ≤ di那么下一时间段该湖将不再有鱼。每个湖的钓鱼时间必须是5 分钟的整数倍。假设没有其他人影响鱼的数量。你的任务是帮助 John 规划每个湖停留的时间使得总钓鱼数量最大。输入格式包含多组测试数据每组第一行是整数 n湖的数量第二行是整数 h可用时间单位小时第三行是 n 个整数fi每个湖初始鱼数第四行是 n 个整数di每个湖递减量第五行是 n-1 个整数ti湖之间的移动时间单位为 5 分钟当 n 0 时输入结束。输出格式对于每组数据输出一行每个湖停留的时间单位分钟用逗号分隔再输出一行Number of fish expected: 最大鱼数不同测试用例之间输出一个空行注意重要如果存在多个最优方案优先选择在湖 1 停留时间更长的方案若仍相同再比较湖 2依此类推即按字典序优先最大化前面的湖停留时间示例输入2 1 10 1 2 5 2 4 4 10 15 20 17 0 3 4 3 1 2 3 4 4 10 15 50 30 0 3 4 3 1 2 3 0示例输出45, 5 Number of fish expected: 31 240, 0, 0, 0 Number of fish expected: 480 115, 10, 50, 35 Number of fish expected: 724题目分析很好你这个总结已经接近“标准题解表达”了我帮你稍微润色 补一个具体例子让它变成考试满分级别的答案。完整思路我们的钓鱼次数是有限的每 5 分钟可以进行一次决策。为了让总收益最大化在每一次钓鱼时都应该选择当前能获得鱼最多的湖。由于每个湖的鱼量会随着时间递减因此这是一个动态最优选择问题可以使用⭐优先队列大根堆维护当前每个湖的收益但本题还有一个重要限制❗ 只能从 1 号湖往后走不能随意选择湖因此我们必须 外层策略枚举终点 k我们枚举最多可以走到哪个湖1 ~ k因为走到更远的湖需要时间如果时间不够就不能到达。 内层策略贪心分配时间在固定的 1 ~ k 范围内每 5 分钟做一次决策从当前所有湖中选鱼最多的湖钓鱼后该湖鱼量减少再放回堆 最终策略在所有 k 的方案中选择✔ 总收益最大的方案✔ 若相同按题目要求字典序优先代码#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);boolfirsttrue;while(true){intn;cinn;if(!cin||n0)break;inth;cinh;vectorintf(n),d(n),t(n);for(inti0;in;i)cinf[i];for(inti0;in;i)cind[i];for(inti0;in-1;i)cint[i];intTh*12;// 转换成5分钟单位vectorintbest_time(n,0);intbest_fish-1;for(intk0;kn;k){inttravel0;for(inti0;ik;i)travelt[i];intremainT-travel;if(remain0)continue;vectorintcur_ff;vectorinttime(n,0);// 大根堆鱼多优先编号小优先关键priority_queuepairint,intpq;for(inti0;ik;i){pq.push({cur_f[i],-i});// 用 -i 保证编号小优先}inttotal0;for(inti0;iremain;i){auto[fish,neg_id]pq.top();pq.pop();intid-neg_id;totalfish;time[id];cur_f[id]max(0,cur_f[id]-d[id]);pq.push({cur_f[id],-id});}// 更新最优解if(totalbest_fish){best_fishtotal;best_timetime;}elseif(totalbest_fish){if(timebest_time){best_timetime;}}}// 输出if(!first)cout\n;firstfalse;for(inti0;in;i){if(i)cout, ;coutbest_time[i]*5;}cout\n;coutNumber of fish expected: best_fish\n;}return0;}