当前位置: 首页 > news >正文

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∼58
6∼1010^3
11∼1310^5A
14∼1610^5B
17∼2010^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 个站点&#xff0c;编号为从 1 到 n。 其中站点 i 与站点 i1 的距离为 vi 公里。 公路上每个站点都可以加油&…...

【LeetCode打卡】Day23|669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树

学习目标&#xff1a; 669. 修剪二叉搜索树 108.将有序数组转换为二叉搜索树 538.把二叉搜索树转换为累加树 学习内容&#xff1a; 669. 修剪二叉搜索树 题目链接&&文章讲解 给你二叉搜索树的根节点 root &#xff0c;同时给定最小边界low 和最大边界 high。通过修剪…...

Transformer位置表示(Position Encoding)

为什么需要位置表示 对比CNN、RNN和Self-Attention: CNN处理相邻窗口的内容&#xff1b;RNN天然是序列操作&#xff0c;考虑了位置先后关系&#xff1b;Self-Attention的计算时是无序的&#xff0c;所以需要位置表示来知道Token之间的位置信息。 绝对位置表示 典型如&#xf…...

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初始化服务&#xff08;详细&#xff09; AliLinux是基于CentOS的。 1、java 环境 2、mysql环境 3、kafka环境 4、flink环境 5、dinky环境 这些环境&#xff0c;本想直接dnf安装在宿主机上&#xff0c;思来想去&#xff0c;还是用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 结论 论文题目&#xff1a; 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)及其用法。 代码示例&#xff1a; 解答思路&#xff1a; 解释一下Python中的装饰器(Decorator)及其作用。 代码示例&#xff1a; 输出&#xff1a; 解答思路&#xff1a; 谈谈Python中的GIL(Global Interprete…...

如何系统地自学Python?

如何系统地自学Python&#xff1f; 如何系统地自学Python&#xff1f;1.了解编程基础2.学习Python基础语法3.学习Python库和框架4.练习编写代码5.参与开源项目6.加入Python社区7.利用资源学习8.制定学习计划9.持之以恒总结 如何系统地自学Python&#xff1f; 作为一个Python语…...

mysql 2-21

约束的分类 添加约束 查看表约束 非空约束 唯一性约束 复合的唯一性约束 只要有一个字段不重复&#xff0c;就可以添加成功 主键约束 自增列 mysql 8.0具有持久化&#xff0c;重启服务器会继续自增 外键约束 创建外键 关联必须有唯一性约束&#xff0c;或者是主键 约束等级 …...

【C#】List泛型数据集如何循环移动,最后一位移动到第一位,以此类推

欢迎来到《小5讲堂》 大家好&#xff0c;我是全栈小5。 这是《C#》系列文章&#xff0c;每篇文章将以博主理解的角度展开讲解&#xff0c; 特别是针对知识点的概念进行叙说&#xff0c;大部分文章将会对这些概念进行实际例子验证&#xff0c;以此达到加深对知识点的理解和掌握。…...

LeetCode23.合并K个升序链表

题目 给你一个链表数组&#xff0c;每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中&#xff0c;返回合并后的链表。 示例 &#xff1a; 输入&#xff1a;lists [[1,4,5],[1,3,4],[2,6]] 输出&#xff1a;[1,1,2,3,4,4,5,6] 解释&#xff1a;链表数组如下&…...

(01)Hive的相关概念——架构、数据存储、读写文件机制

目录 一、架构及组件介绍 1.1 Hive整体架构 1.2 Hive组件 1.3 Hive数据模型&#xff08;Data Model&#xff09; 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 读取文件的过程 …...

二维码扫码登录原理,其实比你想的要简单的多

二维码&#xff0c;大家再熟悉不过了 购物扫个码&#xff0c;吃饭扫个码&#xff0c;坐公交也扫个码 在扫码的过程中&#xff0c;大家可能会有疑问&#xff1a;这二维码安全吗&#xff1f; 会不会泄漏我的个人信息&#xff1f; 更深度的用户还会考虑&#xff1a;我的系统是不…...

Java 实现 Awaitable(多线程并行等待,类似 AutoEventReset 的作用)

AutoEventReset、ManualEventReset&#xff0c;是我们在多线程并行编程之中常常需要涉及的&#xff0c;但是 ManualEventReset 可能用的并没有那么多&#xff0c;这个多用于实现读写锁的&#xff0c;当然 Java 自己库提供了官方实现&#xff0c;就没必要自己去整了。 C/C 里面…...

AI之Sora:Sora(文本指令生成视频的里程碑模型)的简介(能力/安全性/技术细节)、使用方法、案例应用之详细攻略

AI之Sora&#xff1a;Sora(文本指令生成视频的里程碑模型)的简介(能力/安全性/技术细节)、使用方法、案例应用之详细攻略 导读&#xff1a;Sora 是OpenAI研发的一个可以根据文字描述生成视频的AI模型。它的主要特性、功能以及OpenAI在安全和应用方面的策略的核心要点如下所示&a…...

IListManger feeds流

目的:将feeds的分页加载和下拉刷新,与网络请求关联起来 ListLibRecyclerViewProxy 在this.getRecyclerView().addOnScrollListener中记录事件 recyclerView.computeVerticalScrollOffset() // 已经向下滚动的距离,为0时表示已处于顶部。 recyclerView.computeVerticalScro…...

视频推拉流EasyDSS视频直播点播平台授权出现激活码无效并报错400是什么原因?

视频推拉流EasyDSS视频直播点播平台集视频直播、点播、转码、管理、录像、检索、时移回看等功能于一体&#xff0c;可提供音视频采集、视频推拉流、播放H.265编码视频、存储、分发等视频能力服务&#xff0c;在应用场景上&#xff0c;平台可以运用在互联网教育、在线课堂、游戏…...

设计模式三:工厂模式

工厂模式包括简单工厂模式、工厂方法模式和抽象工厂模式&#xff0c;其中后两者属于23中设计模式 各种模式中共同用到的实体对象类&#xff1a; //汽车类&#xff1a;宝马X3/X5/X7&#xff1b;发动机类&#xff1a;B48TU、B48//宝马汽车接口 public interface BMWCar {void s…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

【Ftrace 专栏】Ftrace 参考博文

ftrace、perf、bcc、bpftrace、ply、simple_perf的使用Ftrace 基本用法Linux 利用 ftrace 分析内核调用如何利用ftrace精确跟踪特定进程调度信息使用 ftrace 进行追踪延迟Linux-培训笔记-ftracehttps://www.kernel.org/doc/html/v4.18/trace/events.htmlhttps://blog.csdn.net/…...

python可视化:俄乌战争时间线关键节点与深层原因

俄乌战争时间线可视化分析&#xff1a;关键节点与深层原因 俄乌战争是21世纪欧洲最具影响力的地缘政治冲突之一&#xff0c;自2022年2月爆发以来已持续超过3年。 本文将通过Python可视化工具&#xff0c;系统分析这场战争的时间线、关键节点及其背后的深层原因&#xff0c;全面…...

简约商务通用宣传年终总结12套PPT模版分享

IOS风格企业宣传PPT模版&#xff0c;年终工作总结PPT模版&#xff0c;简约精致扁平化商务通用动画PPT模版&#xff0c;素雅商务PPT模版 简约商务通用宣传年终总结12套PPT模版分享:商务通用年终总结类PPT模版https://pan.quark.cn/s/ece1e252d7df...

初级程序员入门指南

初级程序员入门指南 在数字化浪潮中&#xff0c;编程已然成为极具价值的技能。对于渴望踏入程序员行列的新手而言&#xff0c;明晰入门路径与必备知识是开启征程的关键。本文将为初级程序员提供全面的入门指引。 一、明确学习方向 &#xff08;一&#xff09;编程语言抉择 编…...