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

CSP-J 复赛真题 P9749 [CSP-J 2023] 公路

文章目录

  • 前言
  • [CSP-J 2023] 公路
    • 题目描述
    • 输入格式
    • 输出格式
    • 样例 #1
      • 样例输入 #1
      • 样例输出 #1
    • 提示
  • 示例代码
    • 代码解析
    • 思考过程
    • 总结
  • 总结


前言

在CSP-J 2023的复赛中,出现了一道引人注目的题目——“公路”。这道题目不仅考察了选手们对算法的理解和运用能力,还对思维的灵活性提出了挑战。题目设定了一个关于油料消耗和价格优化的问题,让选手在有限的资源和条件下,找到最优的解决方案。在这个过程中,选手们需要充分理解贪心算法的运用,以及对各种情况的应变能力,从而制定出高效的解决策略。通过深入分析题目和设计合理的算法,选手们能够在短时间内求得最优解,展现出他们在编程竞赛中的能力和智慧。


[CSP-J 2023] 公路

[CSP-J 2023] 公路

题目描述

小苞准备开着车沿着公路自驾。

公路上一共有 n n n 个站点,编号为从 1 1 1 n n n。其中站点 i i i 与站点 i + 1 i + 1 i+1 的距离为 v i v_i vi 公里。

公路上每个站点都可以加油,编号为 i i i 的站点一升油的价格为 a i a_i ai 元,且每个站点只出售整数升的油。

小苞想从站点 1 1 1 开车到站点 n n n,一开始小苞在站点 1 1 1 且车的油箱是空的。已知车的油箱足够大,可以装下任意多的油,且每升油可以让车前进 d d d 公里。问小苞从站点 1 1 1 开到站点 n n n,至少要花多少钱加油?

输入格式

输入的第一行包含两个正整数 n n n d d d,分别表示公路上站点的数量和车每升油可以前进的距离。

输入的第二行包含 n − 1 n - 1 n1 个正整数 v 1 , v 2 … v n − 1 v_1, v_2\dots v_{n-1} v1,v2vn1,分别表示站点间的距离。

输入的第三行包含 n n n 个正整数 a 1 , a 2 … a n a_1, a_2 \dots a_n a1,a2an,分别表示在不同站点加油的价格。

输出格式

输出一行,仅包含一个正整数,表示从站点 1 1 1 开到站点 n n n,小苞至少要花多少钱加油。

样例 #1

样例输入 #1

5 4
10 10 10 10
9 8 9 6 5

样例输出 #1

79

提示

【样例 1 解释】

最优方案下:小苞在站点 1 1 1 买了 3 3 3 升油,在站点 2 2 2 购买了 5 5 5 升油,在站点 4 4 4 购买了 2 2 2 升油。

【样例 2】

见选手目录下的 road/road2.in 与 road/road2.ans。

【数据范围】

对于所有测试数据保证: 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1n105 1 ≤ d ≤ 1 0 5 1 \leq d \leq 10^5 1d105 1 ≤ v i ≤ 1 0 5 1 \leq v_i \leq 10^5 1vi105 1 ≤ a i ≤ 1 0 5 1 \leq a_i \leq 10^5 1ai105

测试点 n ≤ n \leq n特殊性质
1 ∼ 5 1\sim 5 15 8 8 8
6 ∼ 10 6\sim 10 610 1 0 3 10^3 103
11 ∼ 13 11\sim 13 1113 1 0 5 10^5 105A
14 ∼ 16 14\sim 16 1416 1 0 5 10^5 105B
17 ∼ 20 17\sim 20 1720 1 0 5 10^5 105
  • 特殊性质 A:站点 1 1 1 的油价最低。
  • 特殊性质 B:对于所有 1 ≤ i < n 1 \leq i < n 1i<n v i v_i vi d d d 的倍数。

示例代码

这段代码的目的是解决问题 CSP-J 2023 公路,通过优化油料购买策略计算从第一个站点到最后一个站点的最小加油花费。以下是对代码的逐行分析和思考过程的介绍。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>using namespace std;using LL = long long;const int N = 1e5 + 10;int v[N], a[N];
int n, d;
int main() {scanf("%d%d", &n, &d);for (int i = 1; i < n; i++) scanf("%d", &v[i]);int mi = INT_MAX;LL ans = 0, s = 0;for (int i = 1; i < n; i++) {scanf("%d", &a[i]);s += v[i];mi = min(mi, a[i]);if (s > 0) {ans += (s + d - 1) / d * mi;s -= (s + d - 1) / d * d;}}printf("%lld\n", ans);return 0;
}

代码解析

  1. 预处理和常量定义

    #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>using namespace std;using LL = long long;const int N = 1e5 + 10;int v[N], a[N];
    int n, d;
    
    • #define _CRT_SECURE_NO_WARNINGS 是为了禁用 Microsoft Visual C++ 中的安全警告。
    • 引入 iostream,使用标准输入输出流。
    • 使用 using LL = long long;long long 类型定义一个别名 LL
    • 定义常量 N,用于定义数组的最大大小。
    • 声明两个数组 va,分别用于存储站点间的距离和油价。
    • 声明整型变量 n(站点数)和 d(每升油可以行驶的距离)。
  2. 输入读取

    scanf("%d%d", &n, &d);
    for (int i = 1; i < n; i++) scanf("%d", &v[i]);
    
    • 使用 scanf 读取站点数和每升油可以行驶的距离。
    • 读取每两个站点之间的距离,存储到数组 v 中。
  3. 初始化变量

    int mi = INT_MAX;
    LL ans = 0, s = 0;
    
    • mi 用于跟踪当前最低的油价,初始化为 INT_MAX
    • ans 用于存储总花费,初始化为 0。
    • s 用于跟踪当前可以行驶的总距离,初始化为 0。
  4. 主循环处理

    for (int i = 1; i < n; i++) {scanf("%d", &a[i]);s += v[i];mi = min(mi, a[i]);if (s > 0) {ans += (s + d - 1) / d * mi;s -= (s + d - 1) / d * d;}
    }
    
    • 在每个循环中读取油价 a[i] 并更新 s(当前可以行驶的总距离)。
    • 更新当前最低油价 mi
    • 如果 s 大于 0(表示还有可行驶的距离):
      • 计算所需油量,使用公式 (s + d - 1) / d 进行上取整,以确保足够的油量能够覆盖当前的距离。
      • 将相应的花费累加到 ans,使用当前最低油价 mi
      • 减去已经消耗的距离。
  5. 输出结果

    printf("%lld\n", ans);
    return 0;
    
    • 输出总花费 ans

思考过程

  • 贪心策略:程序的核心思路是使用贪心策略在每个站点选择最低的油价进行加油。这样可以确保在行驶过程中花费的油钱最少。
  • 距离和油量的计算:在每一步中,累加已经通过的距离,并计算所需的油量。利用 (s + d - 1) / d 进行上取整来计算需要多少升油。
  • 节省计算:使用 s 来表示当前的距离,这样可以避免重复计算,从而提高效率。

总结

这段代码通过有效的贪心策略和对油量与花费的合理计算,达到了从第一个站点到最后一个站点的最小油费计算。通过分步输入和更新当前油价,确保了每次加油都是以最低价格进行,最终输出的总费用是最优解。


总结

通过这道“公路”题目的解答,我们不仅掌握了贪心算法在实际问题中的应用,也锻炼了分析问题和解决问题的能力。在实际的编程竞赛中,题目的设计往往蕴含着丰富的数学和逻辑思维,选手们需要在理解题意的基础上,快速找到切实可行的解决方案。同时,这道题也强调了对数据结构和算法复杂度的理解,让我们在解决问题时,更加注重时间和空间的优化。希望在未来的编程竞赛中,选手们能够继续保持积极的学习态度,不断挑战自我,突破极限。

相关文章:

CSP-J 复赛真题 P9749 [CSP-J 2023] 公路

文章目录 前言[CSP-J 2023] 公路题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示 示例代码代码解析思考过程总结 总结 前言 在CSP-J 2023的复赛中&#xff0c;出现了一道引人注目的题目——“公路”。这道题目不仅考察了选手们对算法的理解和运用能力&#xff0c…...

MeterSphere压测配置说明

在MeterSphere中&#xff0c;执行性能测试时的配置参数对测试结果有重要影响。以下是对MeterSphere压测配置中几个关键参数的解释&#xff1a; 执行方式&#xff1a;决定了测试的执行模式&#xff0c;例如可以按照持续时间或迭代次数来执行测试。 按持续时间&#xff1a;在这种…...

数据库软题6.1-关系模式-关系模式的各种键

关系模式的各种键 题1-由关系模式求候选键 1. 候选键唯一不冗余 对选项进行闭包运算&#xff0c;如果得到全部属性U&#xff0c;则为候选码 A:AC-ABC-ABCD B:AB-ABC-ABCD C:AE-ABE-ABCE -ABCDE-ABCDEH D:DE2. R的候选码可以从A1,A2,A3,A1A2,A1A3,A2A3,A1A2A3中选择&#xff…...

ulimit:资源限制

一、命令简介 ​ulimit​ 是一个用于资源管理的工具&#xff0c;对于确保系统资源的合理分配和安全使用至关重要。 ‍ 使用场景&#xff1a; 系统管理&#xff1a;限制用户进程使用的资源&#xff0c;防止资源滥用&#xff0c;保证系统稳定。调试&#xff1a;调整核心文件大…...

解决Python使用Selenium 时遇到网页 <body> 划不动的问题

如果在使用 Selenium 时遇到网页的 <body> 划不动的问题&#xff0c;这通常是因为页面的滚动机制&#xff08;例如&#xff0c;可能使用了一个具有固定高度的容器或自定义的滚动条&#xff09;导致无法通过简单的 JavaScript 实现滚动。可以通过以下方法来解决该问题。 …...

pytorch版本和cuda版本不匹配问题

文章目录 &#x1f315;问题&#xff1a;Python11.8安装pytorch11.3失败&#x1f315;CUDA版本和pytorch版本的关系&#x1f315;安装Pytorch2.0.0&#x1f319;pip方法&#x1f319;cuda方法 &#x1f315;问题&#xff1a;Python11.8安装pytorch11.3失败 &#x1f315;CUDA版…...

Vue/组件的生命周期

这篇文章借鉴了coderwhy大佬的Vue生命周期 在Vue实例化或者创建组件的过程中 内部涉及到一系列复杂的阶段 每一个阶段的前后时机都可能对应一个钩子函数 以下是我根据coderwhy大佬文章对于每一个阶段的一些看法 1.过程一 首先实例化Vue或者组件 在实例化之前 会对应一个钩子函…...

【Nacos架构 原理】内核设计之Nacos寻址机制

文章目录 前提设计内部实现单机寻址文件寻址地址服务器寻址 前提 对于集群模式&#xff0c;集群内的每个Nacos成员都需要相互通信。因此这就带来一个问题&#xff0c;该以何种方式去管理集群内部的Nacos成员节点信息&#xff0c;即Nacos内部的寻址机制。 设计 要能够感知到节…...

入门案例:mybatis流程,核心,常见错误

入门案例&#xff1a;mybatis执行流程分析 说明&#xff1a; 1.第一步&#xff1a;是从核心配置文件mybatis-config.xml中构建SqlSessionFactory对象&#xff0c;由于核心配置文件mybatis-config.xml中关联了映射文件UserMapper.xml,所以在SqlSessionFactory中也存在映射文件的…...

C++ | Leetcode C++题解之第456题132模式

题目&#xff1a; 题解&#xff1a; class Solution { public:bool find132pattern(vector<int>& nums) {int n nums.size();vector<int> candidate_i {nums[0]};vector<int> candidate_j {nums[0]};for (int k 1; k < n; k) {auto it_i upper_…...

自然语言处理问答系统

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…...

Python的几个高级特性

引言 Python是一种功能强大的编程语言&#xff0c;它简洁的语法和强大的库支持使其成为数据科学和机器学习领域的热门选择。在Python的高级特性中&#xff0c;生成器、迭代器、闭包、装饰器和内置高阶函数是实现高效、优雅代码的关键。本文将逐一介绍这些特性&#xff0c;并提…...

【颜色平衡树 / E】

题目 思路 DFS暴力 60分 代码 #include <bits/stdc.h> using namespace std; const int N 5010; const int M 5010; int h[N], e[M], ne[M], idx; int c[N], f; int ans; void add(int a, int b) // 添加一条边a->b {e[idx] b, ne[idx] h[a], h[a] idx ; } …...

滑动窗口--(中篇)

将X减到0的最小操作数 给你一个整数数组 nums 和一个整数 x 。每一次操作时&#xff0c;你应当移除数组 nums 最左边或最右边的元素&#xff0c;然后从 x 中减去该元素的值。请注意&#xff0c;需要 修改 数组以供接下来的操作使用。 如果可以将 x 恰好 减到 0 &#xff0c;返…...

Java性能调优:实战技巧与最佳实践

引言 Java作为企业级应用开发的首选语言之一&#xff0c;其性能直接影响到系统的响应速度和用户体验。性能调优是一项复杂的工作&#xff0c;涉及多个层面的知识和技术。本文将通过具体的示例&#xff0c;探讨一些常见的性能调优技巧及最佳实践。 1. 了解你的应用程序 示例&…...

排版套料系统设计说明

先上效果图 项目地址 1.产品介绍 产品名称&#xff1a;StreamFit 智能排版套料系统 主要功能&#xff1a; 智能排版优化 功能描述&#xff1a;StreamFit 利用先进的算法技术&#xff0c;自动对各类材料&#xff08;如布料、金属板材、纸张等&#xff09;进行高效排版布局&am…...

算法修炼之路之二分查找

目录 一:三大二分介绍及模板 1.普通二分 2.查找左右边界的二分及模板 二:LeetCode OJ练习 1.第一题 2.第二题 3.第三题 4.第四题 5.第五题 6.第六题 一:三大二分介绍及模板 1.普通二分 这里通过一道题来引出普通二分及模板 LeetCode_704 二分查找 画图分析: 具体代…...

OpenAI预计明年将推出“代理”系统

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…...

每日OJ题_牛客_重排字符串_贪心_C++_Java

目录 牛客_重排字符串_贪心 题目解析 C代码 Java代码 牛客_重排字符串_贪心 重排字符串 (nowcoder.com) 描述&#xff1a; 小红拿到了一个只由小写字母组成的字符串。她准备把这个字符串重排&#xff08;只改变字母的顺序&#xff0c;不改变数量&#xff09; …...

Python 进阶部分详细整理

1. 面向对象编程&#xff08;OOP&#xff09; 面向对象编程 (OOP) 是一种通过将程序中的数据和功能封装为对象的编程范式。OOP 基于四个核心概念&#xff1a;类与对象、继承、封装与多态。 类与对象 类&#xff08;Class&#xff09;&#xff1a;类是创建对象的蓝图或模板。它…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

适应性Java用于现代 API:REST、GraphQL 和事件驱动

在快速发展的软件开发领域&#xff0c;REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名&#xff0c;不断适应这些现代范式的需求。随着不断发展的生态系统&#xff0c;Java 在现代 API 方…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...

Android写一个捕获全局异常的工具类

项目开发和实际运行过程中难免会遇到异常发生&#xff0c;系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler&#xff0c;它是Thread的子类&#xff08;就是package java.lang;里线程的Thread&#xff09;。本文将利用它将设备信息、报错信息以及错误的发生时间都…...

二维FDTD算法仿真

二维FDTD算法仿真&#xff0c;并带完全匹配层&#xff0c;输入波形为高斯波、平面波 FDTD_二维/FDTD.zip , 6075 FDTD_二维/FDTD_31.m , 1029 FDTD_二维/FDTD_32.m , 2806 FDTD_二维/FDTD_33.m , 3782 FDTD_二维/FDTD_34.m , 4182 FDTD_二维/FDTD_35.m , 4793...