题解：P13882 [蓝桥杯 2023 省 Java A] 小蓝的旅行计划

挺可爱的反悔贪心，乍一看没看出和旅行家的预算的区别，甚至做完才发现不一样的说。

正文

首先我们可以将操作分为两个部分。分别是用油操作和加油操作。

用油

有一个简单的贪心策略，用油的时候首先使用最便宜的油，这点显然。

此外，如果当前油箱里所有油都不能到达下一站，自然就是无解，输出 \(-1\)。

加油

这一部分稍微复杂点，我们显然是不太知道要加多少油的，那不妨直接全加，加到油箱满了为止，然后再把油箱里贵的油退出去，加入更便宜的油。

那可能就会导致浪费，钱算多了怎么办？

我们可以将油想象成一种只有用了才会计算价钱的东西，将花钱挪到用油的部分里面，用一点油，花一点钱就可以了。

实现细节

1. 计算花费要开 long long。
2. 每个站点只加一次油，而不是将油分开一点一点加，否则无法保证复杂度。

还有什么不明白的可以看代码，我这里给出一种 multiset 的实现。

代码

// code by 樓影沫瞬_Hz17
#include <bits/stdc++.h>
using namespace std;#define getc() getchar_unlocked()
#define putc(a) putchar_unlocked(a)
#define en_ putc('\n')
#define e_ putc(' ')using lint = long long;
using pii = pair<int, int>;template<class T> inline T in() { T n = 0; char p = getc();while (p < '-') p = getc();bool f = p == '-' ? p = getc() : 0;do n = n * 10 + (p ^ 48), p = getc();while (isdigit(p));return f ? -n : n;
}
template<class T> inline T in(T &a) { return a = in<T>(); }template<class T> inline void out(T n) {if(n < 0) putc('-'), n = -n;if(n > 9) out(n / 10);putc(n % 10 + '0');
}const int N = 2e5 + 10, B = 560;int dis[N], c[N], lim[N];signed main() {#ifndef ONLINE_JUDGEfreopen("i", "r", stdin);freopen("o", "w", stdout);#endifint n = in<int>(), m = in<int>(), sum = m; // sum 是当前油量lint cost = 0;for(int i = 1; i <= n; i ++) {in(dis[i]), in(c[i]), in(lim[i]);}// 不用 set 因为 set 会去重（虽然这题没差）multiset<pii> e; // 用 pair，第一维用来排序，是价格，第二维自然就是油量e.insert({0, m}); // 给不会 set 的补充一下：insert 用来给 set 插入东西for(int i = 1; i <= n; i ++) {while(dis[i] != 0) {if(e.empty()) { // 油箱空了就无解out(-1);exit(0);}int t = e.begin()->second, k = e.begin()->first, red = min(dis[i], t);e.erase(e.find(*e.begin())); // begin 返回 set 中最小值的指针//erase 用来删除 set 的中某值或某指针的所在// 这里先 find 再 erase 是为了只删一个，否则会删除某个值的所有所在dis[i] -= red, t -= red, sum -= red;cost += 1ll * k * red;if(t) e.insert({k, t}); // 这几行是跑路的过程，注意实现细节。 }int ine = 0; // 记录加多少while(lim[i] != 0) {if(sum < m) {int add = min(lim[i], m - sum); // 油箱没满就加满lim[i] -= add, sum += add;ine += add;}else {if(e.empty()) break; // 不然就用便宜油代替贵油int t = e.rbegin()->second, k = e.rbegin()->first, red = min(lim[i], t);if(k <= c[i]) break; // rbegin == end - 1，即最大值e.erase(e.find(*e.rbegin()));t -= red, lim[i] -= red;ine += red;if(t) e.insert({k, t});}}e.insert({c[i], ine}); // 必须只加一次，否则复杂度无保证}out(cost); en_;
}   
// 星間~ 干渉~ 融解~ 輪迴~ 邂逅~ 再生~ ララバイ~