蓝桥杯省赛真题解析：用线段树+优先队列搞定‘小蓝的旅行计划’（附Java完整代码）
蓝桥杯省赛算法精解：线段树与优先队列在旅行加油问题中的协同应用
第一次看到"小蓝的旅行计划"这道题时，很多选手会被题目中复杂的加油规则和油箱限制条件弄得晕头转向。这道来自蓝桥杯省赛的真题，表面上看是一个简单的贪心问题，但深入分析后会发现它巧妙地融合了区间维护和动态决策两大算法难点。本文将带你从问题本质出发，通过线段树与优先队列的协同工作，找到最优解的实现路径。
1. 问题重述与核心难点分析
题目描述小蓝需要驾驶汽车穿越一系列加油站，每个加油站i有三个关键参数：
- 到达下一个加油站的距离dis[i]
- 当前加油站的油价cost[i]
- 该加油站单次加油量的上限lim[i]
油箱总容量为m，要求计算出完成整个旅程的最小油费。如果没有可行方案，则返回-1。
为什么简单的优先队列解法会失效？
初看这个问题，很多同学会想到用优先队列（最小堆）来维护油价最低的加油站，采用贪心策略每次在油价最低的站点加油。这种方法在没有油箱限制时确实有效，但引入油箱容量限制后会出现两个致命问题：
- 油量动态变化难以追踪：在某站加油后，后续站点的剩余油量状态都会改变
- 区间最大值维护需求：需要知道两个加油站之间行驶过程中的最大油量消耗
// 简单优先队列解法的问题示例 PriorityQueue<GasStation> 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[rt<<1], maxRest[rt<<1|1]); } void pushDown(int rt) { if(lazy[rt] != 0) { lazy[rt<<1] += lazy[rt]; lazy[rt<<1|1] += lazy[rt]; maxRest[rt<<1] += lazy[rt]; maxRest[rt<<1|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, rt<<1)); if(R > mid) res = Math.max(res, query(L, R, mid+1, r, rt<<1|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, rt<<1); if(R > mid) update(L, R, val, mid+1, r, rt<<1|1); pushUp(rt); } }2.2 优先队列的优化使用
优先队列需要存储加油站信息并按油价排序，但需要注意：
- 动态调整：当某加油站的剩余可加油量为0时，需从队列中移除
- 批量处理：当油量不足时，可能需要连续从多个低价加油站加油
PriorityQueue<GasStation> queue = new PriorityQueue<>( (a, b) -> Long.compare(a.cost, b.cost) ); // 加油站类定义 class GasStation { int id; long cost; int limit; // 构造函数等... }3. 关键算法步骤详解
3.1 初始化阶段
- 构建空的线段树，用于维护各站点的油量信息
- 将所有加油站按油价排序存入优先队列
- 初始化当前油量vol = 油箱容量m
SegmentTree st = new SegmentTree(n); PriorityQueue<GasStation> queue = new PriorityQueue<>(); for(int i = 0; i < n; i++) { queue.add(new GasStation(i, cost[i], lim[i])); } int vol = m;3.2 主循环处理
对于每个加油站i（1 ≤ 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 Comparable<GasStation> { 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[rt<<1], maxRest[rt<<1|1]); } void pushDown(int rt) { if(lazy[rt] != 0) { lazy[rt<<1] += lazy[rt]; lazy[rt<<1|1] += lazy[rt]; maxRest[rt<<1] += lazy[rt]; maxRest[rt<<1|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, rt<<1)); if(R > mid) res = Math.max(res, query(L, R, mid+1, r, rt<<1|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, rt<<1); if(R > mid) update(L, R, val, mid+1, r, rt<<1|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); PriorityQueue<GasStation> 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());对于树状数组和线段树的选用，虽然两者都能解决区间查询问题，但在这个问题中线段树更合适，因为：
- 需要支持区间更新操作
- 查询的是区间最大值而非简单求和
- 代码结构更清晰，易于调试
在真实的竞赛场景中，建议先写出基础版本确保正确性，再根据时间限制决定是否进行常数优化。这道题的解题过程很好地展示了如何将现实问题抽象为算法模型，并通过数据结构的组合应用来解决复杂约束条件下的优化问题。