CSP-J 2023 复赛第2题:公路 ← 贪心算法
【题目来源】
https://www.luogu.com.cn/problem/P9749
https://www.acwing.com/problem/content/5311/
【题目描述】
小苞准备开着车沿着公路自驾。
公路上一共有 n 个站点,编号为从 1 到 n。
其中站点 i 与站点 i+1 的距离为 vi 公里。
公路上每个站点都可以加油,编号为 i 的站点一升油的价格为 ai 元,且每个站点只出售整数升的油。
小苞想从站点 1 开车到站点 n,一开始小苞在站点 1 且车的油箱是空的。
已知车的油箱足够大,可以装下任意多的油,且每升油可以让车前进 d 公里。
问小苞从站点 1 开到站点 n,至少要花多少钱加油?
【输入格式】
输入的第一行包含两个正整数 n 和 d ,分别表示公路上站点的数量和车每升油可以前进的距离。
输入的第二行包含 n−1 个正整数 v1,v2,…,vn−1,分别表示站点间的距离。
输入的第三行包含 n 个正整数 a1,a2…an,分别表示在不同站点加油的价格。
【输出格式】
输出一行,仅包含一个正整数,表示从站点 1 开到站点 n,小苞至少要花多少钱加油。
【数据范围】
对于所有测试数据保证:1≤n≤10^5,1≤d≤10^5,1≤vi≤10^5,1≤ai≤10^5。
| 测试点 | n≤ | 特殊性质 |
|---|---|---|
| 1∼5 | 8 | 无 |
| 6∼10 | 10^3 | 无 |
| 11∼13 | 10^5 | A |
| 14∼16 | 10^5 | B |
| 17∼20 | 10^5 | 无 |
特殊性质 A:站点 1 的油价最低。
特殊性质 B:对于所有 1≤i<n,vi 为 d 的倍数。
【输入样例】
5 4
10 10 10 10
9 8 9 6 5
【输出样例】
79
【样例解释】
最优方案下:小苞在站点 1 买了 3 升油,在站点 2 购买了 5 升油,在站点 4 购买了 2 升油。
【算法分析】
很明显的贪心问题,如果第 i 站点的油价较 i+1 的贵,i 站的油只要负责到 i+1 站;
否则 i 站的油要多加,直到遇到比他便宜的站。
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int maxn=1e5+5;
long long v[maxn];
long long a[maxn];
long long fc[maxn];int n,d;
long long ans;
long long price;int main() {cin>>n>>d;for(int i=2; i<=n; i++) {cin>>v[i];v[i]+=v[i-1]; //Distance from site i to the starting pointfc[i]=ceil(1.0*v[i]/d); //Fuel consumption from starting point to current site}for(int i=1; i<=n; i++) cin>>a[i];price=a[1];for(int i=2; i<=n; i++) {ans+=price*(fc[i]-fc[i-1]);price=min(price,a[i]);}cout<<ans;return 0;
}/*
in:
5 4
10 10 10 10
9 8 9 6 5out:
79
*/
【参考文献】
https://www.acwing.com/solution/content/206442/
https://mp.weixin.qq.com/s/zckJsihxsDT2JNBFK1ipxA
https://www.acwing.com/solution/content/220349/
相关文章:
CSP-J 2023 复赛第2题:公路 ← 贪心算法
【题目来源】https://www.luogu.com.cn/problem/P9749https://www.acwing.com/problem/content/5311/【题目描述】 小苞准备开着车沿着公路自驾。 公路上一共有 n 个站点,编号为从 1 到 n。 其中站点 i 与站点 i1 的距离为 vi 公里。 公路上每个站点都可以加油&…...
【LeetCode打卡】Day23|669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树
学习目标: 669. 修剪二叉搜索树 108.将有序数组转换为二叉搜索树 538.把二叉搜索树转换为累加树 学习内容: 669. 修剪二叉搜索树 题目链接&&文章讲解 给你二叉搜索树的根节点 root ,同时给定最小边界low 和最大边界 high。通过修剪…...
Transformer位置表示(Position Encoding)
为什么需要位置表示 对比CNN、RNN和Self-Attention: CNN处理相邻窗口的内容;RNN天然是序列操作,考虑了位置先后关系;Self-Attention的计算时是无序的,所以需要位置表示来知道Token之间的位置信息。 绝对位置表示 典型如…...
LPDDR6与LPDDR5 State Diagram技术探讨
相对于LPDDR5: 1)去掉DSM 2)idle到per-bank-refresh变成per-2-bank-refresh,LPDDR6下可自由组合任两个bank刷新,以提高性能 3)sref到进入command bus training后可MRR、MRW、CAS、MPC等命令 4)idle power down期间可MRR、MRW、CAS、MPC等命令 5)idle到进入command bus train…...
AliLinux的使用Docker初始化服务(详细)
AliLinux的使用Docker初始化服务(详细) AliLinux是基于CentOS的。 1、java 环境 2、mysql环境 3、kafka环境 4、flink环境 5、dinky环境 这些环境,本想直接dnf安装在宿主机上,思来想去,还是用docker方便学习&…...
docker环境常用容器安装
目录 1.安装partainer 2.安装myql 3.安装redis 4.安装Minio 5.安装zibkin 6.安装nacos 7.安装RabbitMq 8.安装RocketMq 8.1启动service 8.2修改对应配置 8.3启动broker 8.4启动控制台 9.安装sentinel 10.安装elasticsearch 11.安装Kibana 12.安装logstash/file…...
【论文阅读|基于 YOLO 的红外小目标检测的逆向范例】
基于 YOLO 的红外小目标检测的逆向范例 摘要1 引言2 相关工作2.1 逆向推理2.2 物体检测方法 3 方法3.1 总体架构3.2 逆向标准的可微分积分 4 实验4.1 数据集和指标4.2 实验环境4.4 OL-NFA 为少样本环境带来稳健性 5 结论 论文题目: A Contrario Paradigm for YOLO-b…...
【presto权威指南】常用操作
shell ./bin/launcher start ./bin/launcher status ./bin/launcher stop /home/work/presto/bin/presto --server hadoop2:8443 --catalog hive --schema defult --debug --user ‘sdfyypt_2_0_eywa_admin’ //指定用户 presto -f 可以指定执行sql文件 presto -execute 可以…...
Python程序员面试准备:八股文题目与解答思路
目录 描述一下Python中的列表推导式(List Comprehension)及其用法。 代码示例: 解答思路: 解释一下Python中的装饰器(Decorator)及其作用。 代码示例: 输出: 解答思路: 谈谈Python中的GIL(Global Interprete…...
如何系统地自学Python?
如何系统地自学Python? 如何系统地自学Python?1.了解编程基础2.学习Python基础语法3.学习Python库和框架4.练习编写代码5.参与开源项目6.加入Python社区7.利用资源学习8.制定学习计划9.持之以恒总结 如何系统地自学Python? 作为一个Python语…...
mysql 2-21
约束的分类 添加约束 查看表约束 非空约束 唯一性约束 复合的唯一性约束 只要有一个字段不重复,就可以添加成功 主键约束 自增列 mysql 8.0具有持久化,重启服务器会继续自增 外键约束 创建外键 关联必须有唯一性约束,或者是主键 约束等级 …...
【C#】List泛型数据集如何循环移动,最后一位移动到第一位,以此类推
欢迎来到《小5讲堂》 大家好,我是全栈小5。 这是《C#》系列文章,每篇文章将以博主理解的角度展开讲解, 特别是针对知识点的概念进行叙说,大部分文章将会对这些概念进行实际例子验证,以此达到加深对知识点的理解和掌握。…...
LeetCode23.合并K个升序链表
题目 给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。 示例 : 输入:lists [[1,4,5],[1,3,4],[2,6]] 输出:[1,1,2,3,4,4,5,6] 解释:链表数组如下&…...
(01)Hive的相关概念——架构、数据存储、读写文件机制
目录 一、架构及组件介绍 1.1 Hive整体架构 1.2 Hive组件 1.3 Hive数据模型(Data Model) 1.3.1 Databases 1.3.2 Tables 1.3.3 Partitions 1.3.4 Buckets 二、Hive读写文件机制 2.1 SerDe 作用 2.2 Hive读写文件流程 2.2.1 读取文件的过程 …...
二维码扫码登录原理,其实比你想的要简单的多
二维码,大家再熟悉不过了 购物扫个码,吃饭扫个码,坐公交也扫个码 在扫码的过程中,大家可能会有疑问:这二维码安全吗? 会不会泄漏我的个人信息? 更深度的用户还会考虑:我的系统是不…...
Java 实现 Awaitable(多线程并行等待,类似 AutoEventReset 的作用)
AutoEventReset、ManualEventReset,是我们在多线程并行编程之中常常需要涉及的,但是 ManualEventReset 可能用的并没有那么多,这个多用于实现读写锁的,当然 Java 自己库提供了官方实现,就没必要自己去整了。 C/C 里面…...
AI之Sora:Sora(文本指令生成视频的里程碑模型)的简介(能力/安全性/技术细节)、使用方法、案例应用之详细攻略
AI之Sora:Sora(文本指令生成视频的里程碑模型)的简介(能力/安全性/技术细节)、使用方法、案例应用之详细攻略 导读:Sora 是OpenAI研发的一个可以根据文字描述生成视频的AI模型。它的主要特性、功能以及OpenAI在安全和应用方面的策略的核心要点如下所示&a…...
IListManger feeds流
目的:将feeds的分页加载和下拉刷新,与网络请求关联起来 ListLibRecyclerViewProxy 在this.getRecyclerView().addOnScrollListener中记录事件 recyclerView.computeVerticalScrollOffset() // 已经向下滚动的距离,为0时表示已处于顶部。 recyclerView.computeVerticalScro…...
视频推拉流EasyDSS视频直播点播平台授权出现激活码无效并报错400是什么原因?
视频推拉流EasyDSS视频直播点播平台集视频直播、点播、转码、管理、录像、检索、时移回看等功能于一体,可提供音视频采集、视频推拉流、播放H.265编码视频、存储、分发等视频能力服务,在应用场景上,平台可以运用在互联网教育、在线课堂、游戏…...
设计模式三:工厂模式
工厂模式包括简单工厂模式、工厂方法模式和抽象工厂模式,其中后两者属于23中设计模式 各种模式中共同用到的实体对象类: //汽车类:宝马X3/X5/X7;发动机类:B48TU、B48//宝马汽车接口 public interface BMWCar {void s…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
PL0语法,分析器实现!
简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
