最小堆（优先队列）和区间树（线段树，红黑树）的结合
java中有自己实现这两种数据结构的对象
（1）最小堆（优先队列）
PriorityQueue<int[]> minHeap = new PriorityQueue<>(new Comparator<int[]>() {// int[] 三个元素 第一个cost 第二个lim 第三个tag
@Override
public int compare(int[] m1, int[] m2) {
// TODO Auto-generated method stub
return m1[0] - m2[0];
}
});//PriorityQueue 默认实现最小堆
（2）区间树（线段树，红黑树）
TreeMap<Integer, Integer> root = new TreeMap<>();// 第一个integer index 第二个integer maxvalue
//这个数据对象底层使用的就是红黑树，内部有`key-value`对
再TreeMap中，由于只存在key-value对，对于
（1）只在区间上的问题，如2023蓝桥杯 java A组 太阳我们可以把[left,right]中left作为key，right作为value，通过floorEntry()这个函数访问需要的节点。
（2）对于需要再区间内部操作的问题，如求某个区间的和，或者某个区间的最大值，我们没有额外的数据域去保存这个sum或max（如本题）。这个时候就可以采用，类似二分的方法，自定义key（1-n）来利用TreeMap制作区间树
代码如下
import java.math.BigInteger;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeMap;
public class Main {
static int[] dis = new int[200001];
static int[] cost = new int[200001];
static int[] lim = new int[200001];
static int n;
static void build(TreeMap<Integer, Integer> root, int left, int right, int index) {
if (left == right) {
root.put(index, 0);
return;
}
int mid = (left + right) >> 1;
build(root, left, mid, index * 2);
build(root, mid + 1, right, index * 2 + 1);
root.put(index, Math.max(root.get(2 * index), root.get(2 * index + 1)));
}
static void update(TreeMap<Integer, Integer> root, int i, int j, int temp2) {
update(root, 1, n, i, j, temp2, 1);
}
static void update(TreeMap<Integer, Integer> root, int left, int right, int i, int j, int temp2, int index) {
if (right < i || left > j)
return;
if (left == right) {
root.put(index, root.get(index) + temp2);
return;
}
int mid = (left + right) >> 1;
update(root, left, mid, i, j, temp2, index * 2);
update(root, mid + 1, right, i, j, temp2, index * 2 + 1);
root.put(index, Math.max(root.get(index * 2), root.get(index * 2 + 1)));
}
static int query(TreeMap<Integer, Integer> root, int i, int j) {
return query(root, 1, n, i, j, 1);
}
static int query(TreeMap<Integer, Integer> root, int left, int right, int i, int j, int index) {
if (left >= i && right <= j)
return root.get(index);
if (right < i || left > j)
return Integer.MIN_VALUE;
int mid = (left + right) >> 1;
return Math.max(query(root, left, mid, i, j, index * 2), query(root, mid + 1, right, i, j, index * 2 + 1));
}
public static void main(String[] args) {
TreeMap<Integer, Integer> root = new TreeMap<>();// 第一个integer index 第二个integer maxvalue
PriorityQueue<int[]> minHeap = new PriorityQueue<>(new Comparator<int[]>() {// int[] 三个元素 第一个cost 第二个lim 第三个tag
@Override
public int compare(int[] m1, int[] m2) {
// TODO Auto-generated method stub
return m1[0] - m2[0];
}
});
Scanner sc = new Scanner(System.in);
int m;
n = sc.nextInt();
build(root, 1, n, 1);
m = sc.nextInt();
long ans = 0;
for (int i = 1; i <= n; i++) {
dis[i] = sc.nextInt();
cost[i] = sc.nextInt();
lim[i] = sc.nextInt();
}
int oil = m;
for (int i = 1; i <= n; i++) {
while (oil < dis[i]) {
if (minHeap.size() == 0) {
System.out.println("-1");
return;
}
int[] temp = minHeap.poll();
if (query(root, temp[2], i - 1) == m)
continue;
int temp1 = m - query(root, temp[2], i - 1);
int temp2 = Math.min(temp1, Math.min(temp[1], dis[i] - oil));
ans += temp2 * temp[0];
oil += temp2;
if (temp[1] - temp2 > 0)
minHeap.add(new int[] { temp[0], temp[1] - temp2, temp[2] });
update(root, temp[2], i - 1, temp2);
}
oil -= dis[i];
if (oil > 0)
update(root, i, i, oil);
minHeap.add(new int[] { cost[i], lim[i], i });
}
System.out.println(ans);
}
}
最小堆维护的数据
加油站的价格，这样可以从堆顶知道便宜的加油站在哪
区间树维护的数据
在每个加油站存在最多油的数量
思路解析
这个思路的关键之处在于int temp2 = Math.min(temp1, Math.min(temp[1], dis[i] - oil));
在过去的便宜加油站加油，并不是指再返程回去，而是说，在便宜加油站直接加够这一次也需要的油，但是这也意味着从便宜加油站到此处，你一直携带者下段路程油，那在这个携带过程中，任何一处，携带的油加上当时需要的油不要超过m
在这个关键之处三个变量temp1 temp[1]和dis[i]-oil所代表的含义如下
（1）temp1在int temp1 = m - query(root, temp[2], i - 1);得到，它是指在从便宜加油站到此处你装过最多的油的时候距m还有多少
（2）temp[1]是指便宜加油站处最多能加多少
（3）dis[i]-oil是指走接下来这段路你还差多少油，没必要有多少加多少，万一下一加油站极其便宜呢