蓝桥杯省赛真题解析：用线段树+优先队列搞定‘小蓝的旅行计划’（附Java完整代码）

蓝桥杯省赛算法精解线段树与优先队列在旅行加油问题中的协同应用第一次看到小蓝的旅行计划这道题时很多选手会被题目中复杂的加油规则和油箱限制条件弄得晕头转向。这道来自蓝桥杯省赛的真题表面上看是一个简单的贪心问题但深入分析后会发现它巧妙地融合了区间维护和动态决策两大算法难点。本文将带你从问题本质出发通过线段树与优先队列的协同工作找到最优解的实现路径。1. 问题重述与核心难点分析题目描述小蓝需要驾驶汽车穿越一系列加油站每个加油站i有三个关键参数到达下一个加油站的距离dis[i]当前加油站的油价cost[i]该加油站单次加油量的上限lim[i]油箱总容量为m要求计算出完成整个旅程的最小油费。如果没有可行方案则返回-1。为什么简单的优先队列解法会失效初看这个问题很多同学会想到用优先队列最小堆来维护油价最低的加油站采用贪心策略每次在油价最低的站点加油。这种方法在没有油箱限制时确实有效但引入油箱容量限制后会出现两个致命问题油量动态变化难以追踪在某站加油后后续站点的剩余油量状态都会改变区间最大值维护需求需要知道两个加油站之间行驶过程中的最大油量消耗// 简单优先队列解法的问题示例 PriorityQueueGasStation queue new PriorityQueue(); queue.addAll(stations); // 无法处理油量限制导致的动态调整2. 算法框架设计双数据结构协同要解决这个难题我们需要设计一个双数据结构系统优先队列负责快速获取当前可选的油价最低加油站线段树实时维护任意区间内的油量最大值2.1 线段树的角色与实现线段树在此问题中主要负责高效处理以下两种操作区间查询查询[i,j]区间内的最大油量值区间更新当在某站加油后更新相关区间的油量值class SegmentTree { int[] maxRest; // 区间最大剩余油量 int[] lazy; // 懒惰标记 void pushUp(int rt) { maxRest[rt] Math.max(maxRest[rt1], maxRest[rt1|1]); } void pushDown(int rt) { if(lazy[rt] ! 0) { lazy[rt1] lazy[rt]; lazy[rt1|1] lazy[rt]; maxRest[rt1] lazy[rt]; maxRest[rt1|1] lazy[rt]; lazy[rt] 0; } } int query(int L, int R, int l, int r, int rt) { if(L l r R) return maxRest[rt]; pushDown(rt); int mid (l r) 1; int res 0; if(L mid) res Math.max(res, query(L, R, l, mid, rt1)); if(R mid) res Math.max(res, query(L, R, mid1, r, rt1|1)); return res; } void update(int L, int R, int val, int l, int r, int rt) { if(L l r R) { lazy[rt] val; maxRest[rt] val; return; } pushDown(rt); int mid (l r) 1; if(L mid) update(L, R, val, l, mid, rt1); if(R mid) update(L, R, val, mid1, r, rt1|1); pushUp(rt); } }2.2 优先队列的优化使用优先队列需要存储加油站信息并按油价排序但需要注意动态调整当某加油站的剩余可加油量为0时需从队列中移除批量处理当油量不足时可能需要连续从多个低价加油站加油PriorityQueueGasStation queue new PriorityQueue( (a, b) - Long.compare(a.cost, b.cost) ); // 加油站类定义 class GasStation { int id; long cost; int limit; // 构造函数等... }3. 关键算法步骤详解3.1 初始化阶段构建空的线段树用于维护各站点的油量信息将所有加油站按油价排序存入优先队列初始化当前油量vol 油箱容量mSegmentTree st new SegmentTree(n); PriorityQueueGasStation queue new PriorityQueue(); for(int i 0; i n; i) { queue.add(new GasStation(i, cost[i], lim[i])); } int vol m;3.2 主循环处理对于每个加油站i1 ≤ i ≤ n消耗dis[i]油量到达该站检查油量是否不足vol 0不足时从优先队列取油价最低的加油站补油处理当前加油站的加油可能性for(int i 1; i n; i) { vol - dis[i]; // 消耗油量到达本站 // 油量不足时的处理 while(vol 0 !queue.isEmpty()) { GasStation best queue.poll(); int maxAdd Math.min( m - st.query(best.id, i-1), // 考虑区间最大油量限制 best.limit // 本站加油上限 ); if(maxAdd 0) continue; if(maxAdd -vol) { // 可以加满需求油量 totalCost best.cost * maxAdd; vol maxAdd; best.limit 0; st.update(best.id, i-1, maxAdd); } else { // 只能加部分油量 totalCost best.cost * (-vol); best.limit maxAdd vol; st.update(best.id, i-1, -vol); queue.add(best); // 放回队列 vol 0; } } if(vol 0) { // 油量仍不足且无加油站可用 System.out.println(-1); return; } // 处理当前加油站 if(vol 0) { st.update(i, i, vol); } queue.add(new GasStation(i, cost[i], Math.min(lim[i], m - vol))); }3.3 复杂度分析该算法的时间复杂度主要来自优先队列操作O(n log n)线段树查询和更新每次O(log n)共O(n log n)总时间复杂度为O(n log n)空间复杂度O(n)完全适用于题目给定的数据范围。4. 完整Java实现与关键注释以下是整合后的完整解决方案包含详细的注释说明import java.util.*; public class TravelPlan { static class GasStation implements ComparableGasStation { int id; long cost; int limit; public GasStation(int id, long cost, int limit) { this.id id; this.cost cost; this.limit limit; } Override public int compareTo(GasStation o) { return Long.compare(this.cost, o.cost); } } static class SegmentTree { int[] maxRest; int[] lazy; int n; public SegmentTree(int n) { this.n n; maxRest new int[4 * n]; lazy new int[4 * n]; } void pushUp(int rt) { maxRest[rt] Math.max(maxRest[rt1], maxRest[rt1|1]); } void pushDown(int rt) { if(lazy[rt] ! 0) { lazy[rt1] lazy[rt]; lazy[rt1|1] lazy[rt]; maxRest[rt1] lazy[rt]; maxRest[rt1|1] lazy[rt]; lazy[rt] 0; } } int query(int L, int R) { return query(L, R, 1, n, 1); } private int query(int L, int R, int l, int r, int rt) { if(L l r R) return maxRest[rt]; pushDown(rt); int mid (l r) 1; int res 0; if(L mid) res Math.max(res, query(L, R, l, mid, rt1)); if(R mid) res Math.max(res, query(L, R, mid1, r, rt1|1)); return res; } void update(int L, int R, int val) { update(L, R, val, 1, n, 1); } private void update(int L, int R, int val, int l, int r, int rt) { if(L l r R) { lazy[rt] val; maxRest[rt] val; return; } pushDown(rt); int mid (l r) 1; if(L mid) update(L, R, val, l, mid, rt1); if(R mid) update(L, R, val, mid1, r, rt1|1); pushUp(rt); } } public static long solve(int m, int[] dis, int[] cost, int[] lim) { int n dis.length - 1; // 假设dis[0]不用从1开始 SegmentTree st new SegmentTree(n); PriorityQueueGasStation queue new PriorityQueue(); for(int i 1; i n; i) { queue.add(new GasStation(i, cost[i], lim[i])); } long totalCost 0; int vol m; for(int i 1; i n; i) { vol - dis[i]; while(vol 0 !queue.isEmpty()) { GasStation best queue.poll(); int maxAdd Math.min( m - st.query(best.id, i-1), best.limit ); if(maxAdd 0) continue; if(maxAdd -vol) { totalCost best.cost * maxAdd; vol maxAdd; best.limit 0; st.update(best.id, i-1, maxAdd); } else { totalCost best.cost * (-vol); best.limit maxAdd vol; st.update(best.id, i-1, -vol); queue.add(best); vol 0; } } if(vol 0) return -1; if(vol 0) { st.update(i, i, vol); } queue.add(new GasStation(i, cost[i], Math.min(lim[i], m - vol))); } return totalCost; } public static void main(String[] args) { // 示例输入 int m 10; int[] dis {0, 2, 3, 5}; // dis[0]不用 int[] cost {0, 3, 2, 4}; // cost[0]不用 int[] lim {0, 5, 3, 2}; // lim[0]不用 long result solve(m, dis, cost, lim); System.out.println(最小油费: result); } }5. 算法优化与边界情况处理在实际编码竞赛中还需要考虑以下优化和边界情况输入输出优化使用BufferedReader代替Scanner处理大规模输入提前终止当油量不足且无加油站可用时立即返回-1初始化检查总距离是否超过初始油量能支持的最大距离零距离站点处理相邻加油站距离为0的特殊情况// 输入优化示例 BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); int m Integer.parseInt(st.nextToken());对于树状数组和线段树的选用虽然两者都能解决区间查询问题但在这个问题中线段树更合适因为需要支持区间更新操作查询的是区间最大值而非简单求和代码结构更清晰易于调试在真实的竞赛场景中建议先写出基础版本确保正确性再根据时间限制决定是否进行常数优化。这道题的解题过程很好地展示了如何将现实问题抽象为算法模型并通过数据结构的组合应用来解决复杂约束条件下的优化问题。