尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
【题解-信息学奥赛一本通】1373:鱼塘钓鱼(fishing)
题目1373鱼塘钓鱼(fishing题目描述有N个鱼塘排成一排N100每个鱼塘中有一定数量的鱼例如N5时如下表鱼塘编号每1分钟能钓到的鱼的数量1…1000每1分钟能钓鱼数的减少量1…100当前鱼塘到下一个相邻鱼塘需要的时间单位分钟鱼塘编号12345每1分钟能钓到的鱼的数量101420169每1分钟能钓鱼数的减少量24653当前鱼塘到下一个相邻鱼塘需要的时间单位分钟3544即在第1个鱼塘中钓鱼第1分钟内可钓到10条鱼第2分钟内只能钓到8条鱼……第5分钟以后再也钓不到鱼了。从第1个鱼塘到第2个鱼塘需要3分钟从第2个鱼塘到第3个鱼塘需要5分钟……给出一个截止时间T(T1000)设计一个钓鱼方案从第1个鱼塘出发希望能钓到最多的鱼。假设能钓到鱼的数量仅和已钓鱼的次数有关且每次钓鱼的时间都是整数分钟。输入共5行分别表示第1行为N第2行为第1分钟各个鱼塘能钓到的鱼的数量每个数据之间用一空格隔开第3行为每过1分钟各个鱼塘钓鱼数的减少量每个数据之间用一空格隔开第4行为当前鱼塘到下一个相邻鱼塘需要的时间第5行为截止时间T。输出一个整数不超过231−1表示你的方案能钓到的最多的鱼。时空限制1s / 64MB样例输入5 10 14 20 16 9 2 4 6 5 3 3 5 4 4 14样例输出76思路y总按照前后反复横跳可以将路线分为两类一类是经过某个点不钓鱼接着回到这点钓鱼后面到其他点钓之后再回到这个点钓鱼。另一类是从第一个点径直走到后面的点如果不再某点钓鱼那么之后也不会返回再钓。由于钓鱼的数量仅与钓鱼时间有关所以第二类路线的钓鱼数量第一类路线的钓鱼数量。在第二类路线中可以细分为n条具体的路径分别是从1-1从1-2从1-2-3…1-2-3…-n。枚举每条具体的路径求全局最优。在每条路径中假设该路径从1-2-3-…m钓鱼时间t总时间-路上花费的时间。要想钓鱼数量最大肯定希望每分钟钓的鱼数量最大。因此问题变成了求m个序列中的前t大元素。可以用大根堆来做。代码#includebits/stdc.husingnamespacestd;typedefpairint,intPII;constintN10010;intn,fish[N],sub[N],tim[N],T,ans;intwork(intm){intfishtimT-tim[m];priority_queuePIIheap;for(inti1;im;i)heap.push({fish[i],i});intk0,sum0;while(!heap.empty()kfishtim){PII theap.top();heap.pop();sumt.first;intit.second;if(t.first-sub[i]0)heap.push({t.first-sub[i],i});k;}returnsum;}intmain(){cinn;for(inti1;in;i)cinfish[i];for(inti1;in;i)cinsub[i];for(inti2;in;i){cintim[i];tim[i]tim[i-1];}cinT;for(inti1;in;i)ansmax(ans,work(i));coutans;return0;}结果
RELATED

相关推荐

聊天机器人、AI助手、AI智能体到底有什么区别?搞懂这层才算真正入门

聊天机器人、AI助手、AI智能体到底有什么区别?搞懂这层才算真正入门

聊天机器人、AI助手、AI智能体到底有什么区别?搞懂这层才算真正入门基于规则或简单模型的问答系统,主要用于FAQ检索和客服首轮分流,比如“怎么退货”“营业时间”这类高频标准问题。遇到超出预设范围的问题,它只能说“这个我不太清…

📅 2026/9/6 0:15:30
7.Java 深度练习

7.Java 深度练习

Java程序的基本结构记住这个模板,以后每个Java文件都长这样:public class‌:声明一个公共类,public表示这个类可以被其他任何类访问;class是定义类的关键字。HelloWorld‌:这是类名。根据 Java 规范&#x…

📅 2026/8/23 1:51:27
Seed-VC模型选择实战:从入门到精通的完整指南

Seed-VC模型选择实战:从入门到精通的完整指南

Seed-VC模型选择实战:从入门到精通的完整指南 【免费下载链接】seed-vc zero-shot voice conversion & singing voice conversion, with real-time support 项目地址: https://gitcode.com/GitHub_Trending/se/seed-vc Seed-VC是一个强大的零样本语音转换…

📅 2026/9/16 5:50:27
MORE NEWS

更多资讯

📰

图解原理:3步搞定如何设置电脑开机密码防黑客

图解原理:3步搞定如何设置电脑开机密码防黑客 版本升级后 API 全变了?别慌,这次我们拆解最底层的逻辑。很多开发者习惯用 sudo 一把梭,却忘了 如何设置电脑开机密码…

📰

3个步骤搞定丫丫项目搭建与源码解析

3个步骤搞定丫丫项目搭建与源码解析 刚毕业拿到 offer,或者准备跳槽面试,你是不是也卡在这个坎上? 书上的语法都背熟了,LeetCode 刷题也顺手,但一让你从 0 到 1 搭个项目,脑子就一片空白。…

📰

袁辉实战:3步搞定源码解析,新手避坑指南

袁辉实战:3步搞定源码解析,新手避坑指南 刚学完 Python 或 Java 的语法,打开编辑器却像无头苍蝇?很多初学者都卡在“学会语法却不知怎么搭项目”这一步。别急,这不是你的错,而是缺少一个从理论到落地的桥梁。今天我们就通过袁辉这个实战…

📰

3步读懂压缩器源码解析 搞定项目搭建难题

3步读懂压缩器源码解析 搞定项目搭建难题 很多开发者卡在“语法会背,项目不会搭”的瓶颈期。你盯着文档里的 compress() 方法发呆,心里想:这底层到底是怎么把数据变小了? 别急,今天咱们不整虚的,直接拆解【压缩器】的【源码解析】。…

📰

烽火机顶盒开发避坑:从零搭建到最佳实践,彻底告别环境卡死

烽火机顶盒开发避坑:从零搭建到最佳实践,彻底告别环境卡死 配置环境就卡半天,是不是让你想砸键盘?别急,这是绝大多数开发者在接触【烽火机顶盒】定制开发时的真实痛点。很多人以为只要会写代码就能搞定,结果在交叉编译、驱动适配、系统裁剪上耗了半个月…

📰

3道口红游戏高频面试题,搞定版本API大坑

3道口红游戏高频面试题,搞定版本API大坑 版本升级后 API 全变了,这是很多后端和全栈开发在接手老项目时最头疼的事。尤其是像口红游戏这种涉及实时状态同步、复杂状态机流转的业务场景,一旦底层通信协议或数据结构发生变动,原本跑得好好的逻辑瞬…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬