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…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...
