域名注册了后怎么建设网站,外链系统,外贸网站建设课本,手机网站模板 网址文章目录 前言[CSP-J 2023] 公路题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示 示例代码代码解析思考过程总结 总结 前言
在CSP-J 2023的复赛中#xff0c;出现了一道引人注目的题目——“公路”。这道题目不仅考察了选手们对算法的理解和运用能力#xff0c… 文章目录 前言[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 i1 的距离为 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 n−1 个正整数 v 1 , v 2 … v n − 1 v_1, v_2\dots v_{n-1} v1,v2…vn−1分别表示站点间的距离。
输入的第三行包含 n n n 个正整数 a 1 , a 2 … a n a_1, a_2 \dots a_n a1,a2…an分别表示在不同站点加油的价格。
输出格式
输出一行仅包含一个正整数表示从站点 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 1≤n≤105 1 ≤ d ≤ 1 0 5 1 \leq d \leq 10^5 1≤d≤105 1 ≤ v i ≤ 1 0 5 1 \leq v_i \leq 10^5 1≤vi≤105 1 ≤ a i ≤ 1 0 5 1 \leq a_i \leq 10^5 1≤ai≤105。
测试点 n ≤ n \leq n≤特殊性质 1 ∼ 5 1\sim 5 1∼5 8 8 8无 6 ∼ 10 6\sim 10 6∼10 1 0 3 10^3 103无 11 ∼ 13 11\sim 13 11∼13 1 0 5 10^5 105A 14 ∼ 16 14\sim 16 14∼16 1 0 5 10^5 105B 17 ∼ 20 17\sim 20 17∼20 1 0 5 10^5 105无
特殊性质 A站点 1 1 1 的油价最低。特殊性质 B对于所有 1 ≤ i n 1 \leq i n 1≤in v i v_i vi 为 d d d 的倍数。
示例代码
这段代码的目的是解决问题 CSP-J 2023 公路通过优化油料购买策略计算从第一个站点到最后一个站点的最小加油花费。以下是对代码的逐行分析和思考过程的介绍。
#define _CRT_SECURE_NO_WARNINGS
#include iostreamusing 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;
}代码解析 预处理和常量定义 #define _CRT_SECURE_NO_WARNINGS
#include iostreamusing 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用于定义数组的最大大小。声明两个数组 v 和 a分别用于存储站点间的距离和油价。声明整型变量 n站点数和 d每升油可以行驶的距离。 输入读取 scanf(%d%d, n, d);
for (int i 1; i n; i) scanf(%d, v[i]);使用 scanf 读取站点数和每升油可以行驶的距离。读取每两个站点之间的距离存储到数组 v 中。 初始化变量 int mi INT_MAX;
LL ans 0, s 0;mi 用于跟踪当前最低的油价初始化为 INT_MAX。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;}
}在每个循环中读取油价 a[i] 并更新 s当前可以行驶的总距离。更新当前最低油价 mi。如果 s 大于 0表示还有可行驶的距离 计算所需油量使用公式 (s d - 1) / d 进行上取整以确保足够的油量能够覆盖当前的距离。将相应的花费累加到 ans使用当前最低油价 mi。减去已经消耗的距离。 输出结果 printf(%lld\n, ans);
return 0;输出总花费 ans。
思考过程
贪心策略程序的核心思路是使用贪心策略在每个站点选择最低的油价进行加油。这样可以确保在行驶过程中花费的油钱最少。距离和油量的计算在每一步中累加已经通过的距离并计算所需的油量。利用 (s d - 1) / d 进行上取整来计算需要多少升油。节省计算使用 s 来表示当前的距离这样可以避免重复计算从而提高效率。
总结
这段代码通过有效的贪心策略和对油量与花费的合理计算达到了从第一个站点到最后一个站点的最小油费计算。通过分步输入和更新当前油价确保了每次加油都是以最低价格进行最终输出的总费用是最优解。 总结
通过这道“公路”题目的解答我们不仅掌握了贪心算法在实际问题中的应用也锻炼了分析问题和解决问题的能力。在实际的编程竞赛中题目的设计往往蕴含着丰富的数学和逻辑思维选手们需要在理解题意的基础上快速找到切实可行的解决方案。同时这道题也强调了对数据结构和算法复杂度的理解让我们在解决问题时更加注重时间和空间的优化。希望在未来的编程竞赛中选手们能够继续保持积极的学习态度不断挑战自我突破极限。
