继续刷 CSP-J 2023 真题。这题考点是贪心先把题意吃透。题目来源ACGO A7124 洛谷 P9749难度定位普及- 通过率41.98%一、题目信息题目名称公路所属赛事2023 年 CSP-J 组复赛官方难度普及-涉及知识点贪心题目链接https://www.acgo.cn/problemset/info/7124洛谷编号P9749同一道题两个平台均可提交代码通用易错点很多人栽在这贪心策略写完先找反例证明不了就别急着交注意排序的稳定性相同关键字的处理顺序可能影响答案题意简述题意其实很直白小苞准备开着车沿着公路自驾。公路上一共有 n 个站点编号为从 1 到 n。其中站点 i 与站点 i 1 的距离为 v_i 公里。公路上每个站点都可以加油编号为 i 的站点一升油的价格为 a_i 元且每个站点只出售整数升的油。小苞想从站点 1 开车到站点 n一开始小苞在站点 1 且车的油箱是空的。已知车的油箱足够大可以装下任意多的油且每升油可以让车前进 d 公里。问小苞从站点 1 开到站点 n至少要花多少钱加油前置知识这题要用到的工具不多但有一个容易忘先过一遍。局部最优推全局贪心的难点是「证明这样贪是对的」。写完代码前先问自己有没有反例换一种贪法会不会更优二、思路分析这题官方难度普及-开考半小时内比较稳妥。思路的入口在哪里可以考虑贪心。首先我们发现在 1 号加油站必须买油否则根本动不了。接下来你可以不断开到在当前加油站后比当前加油站油价低的加油站并使油剩得最少。什么意思拿样例来说就是这样5 410 10 10 109 8 9 6 52 号加油站是我们要开到的第二个加油站因为 2 号加油站的油价oil_2oil_1 同时我们只买 3 升油这样能开到 2 号加油站并使油剩得最少。2 号站后我们要到 4 号站去原因同上。为什么呢假如我们现在有一排加油站第i 个加油站的油价是 i1 站的距离是 dis_i 。你先处理出 1 号加油站到 i 号加油站的总距离 sum_i假如我们现在在 a 号加油站要去 b 号加油站中间有个 c 号加油站且 按照我们的策略我们一定要去 c。三、完整代码#include iostream #include vector #include cstdio using namespace std; // CSP-J 2023 公路 // 站点 i 到 i1 距离 v_i站点 i 每升油 a_i 元每升跑 d 公里。 // 油箱无限大。贪心在「当前能到的站点中价格最低」的那个站尽量加满。 // 具体做法记当前油还能跑 rest 公里到 i 站时。 // 每到一个站若本站价格比后面能到的站都低就加够到下一个更便宜站所需的油。 int main() { int n; long long d; cin n d; vectorlong long v(n 1, 0); // v[i]: i - i1 的距离 for (int i 1; i n - 1; i) cin v[i]; vectorlong long a(n 1); for (int i 1; i n; i) cin a[i]; // 单调栈求每个站点右边第一个价格更小的站点 vectorint nxtSmaller(n 2, n 1); { vectorint stk; for (int i n; i 1; --i) { while (!stk.empty() a[stk.back()] a[i]) stk.pop_back(); nxtSmaller[i] stk.empty() ? (n 1) : stk.back(); stk.push_back(i); } } long long cost 0; long long rest 0; // 到达当前站点时还能跑的公里数 for (int i 1; i n - 1; i) { // 从 i 走到 nxtSmaller[i] 的总距离 int j nxtSmaller[i]; // j n 或 n1 long long need 0; for (int k i; k (j n 1 ? n : j); k) need v[k]; // 在 i 站把油加到「刚好能跑到 j」或「跑完全程」 if (j n 1) { // 后面没有更便宜的直接在这加满到终点 long long total 0; for (int k i; k n - 1; k) total v[k]; if (rest total) { long long buy (total - rest d - 1) / d; // 需要买的升数上取整 cost buy * a[i]; rest buy * d; } break; } else { if (rest need) { long long buy (need - rest d - 1) / d; cost buy * a[i]; rest buy * d; } } rest - v[i]; // 开到 i1 } cout cost \n; return 0; }四、代码分段拆解完整代码在上面下面按功能分块解释。头文件与全局变量先把用到的头文件和全局变量放上来。全局变量在竞赛里很常用好处是函数之间共享方便代价是要小心初始化和被意外改写。#include iostream #include vector #include cstdiousing namespace std; int main() { int n; long long d; vectorlong long v(n 1, 0); // v[i]: i - i1 的距离 vectorlong long a(n 1); vectorint nxtSmaller(n 2, n 1); vectorint stk;主体逻辑主体部分按顺序完成读入、计算、输出。main函数尽量保持线性把复杂的逻辑拆成独立函数出问题时更容易定位。边界处理这类题最容易在边界上翻车最小值、最大值、只剩一个元素的情况都在脑中过一遍。五、实例模拟光看代码容易虚用样例实测一遍最踏实。样例 1输入5 4 10 10 10 10 9 8 9 6 5输出79以第一组样例为例输入是5 4、10 10 10 10、9 8 9 6 5正确输出是79。建议把这两行数据抄在纸上用上面的代码手动走一遍重点看循环变量怎么变化、答案在哪一步被更新。能自己推出来的东西比看懂代码印象深得多。六、踩坑总结最后总结几个要点。贪心策略写完先找反例证明不了就别急着交注意排序的稳定性相同关键字的处理顺序可能影响答案另外提醒一句这题在 CSP-J 2023 里是普及-难度考场上如果没有把握拿满分先把暴力写法交上去拿到部分分再回头优化。CSP 是打分制空着不写才是最亏的。七、知识点拓展这题的核心是贪心。贪心题的正解往往是「排序 一次扫描」。判断能不能贪关键是找一个交换论证如果两个元素的顺序换过来答案不会变差那按某个关键字排序就是对的。建议的练习路径先把本题独立写一遍不看代码遇到卡壳再看提示换个平台提交ACGO 和洛谷都试试确保代码在两个平台都能过找两到三道同类型的题练手巩固这类问题的识别能力八、适用人群这道题的适用面刚学完循环和数组想找真题练手的同学准备 GESP 三到四级、想提前接触 CSP 风格的同学想弄明白贪心类问题标准解法的同学代码有任何问题欢迎指正我会及时更新。关于这个系列这是「CSP 真题逐题精讲」的第 36 篇。我会按年份从 2019 一路刷到 2025CSP-J 和 CSP-S 全覆盖。每篇都给双平台题号ACGO 洛谷 逐行代码拆解 真实样例模拟。跟着刷完这一套CSP 第一轮的选择题和基础题基本就稳了。下一篇CSP-J 2023 一元二次方程普及/提高- 关注我不错过后续更新。评论区告诉我你现在刷到哪一年了我看看能不能按大家的进度调整更新节奏。