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

· · 题解

题解：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;

signed main() {
    #ifndef ONLINE_JUDGE
        freopen("i", "r", stdin);
        freopen("o", "w", stdout);
    #endif
    int n = in<int>(), m = in<int>(), sum = m, dis, c, lim; // sum 是当前油量
    lint cost = 0;
    // 不用 set 因为 set 会去重（虽然这题没差）
    multiset<pii> e; // 用 pair，第一维用来排序，是价格，第二维自然就是油量
    e.insert({0, m}); // 给不会 set 的补充一下：insert 用来给 set 插入东西

    for(int i = 1; i <= n; i ++) {
        in(dis), in(c), in(lim);
        while(dis != 0) {
            if(e.empty()) { // 油箱空了就无解
                out(-1);
                exit(0);
            }
            int t = e.begin()->second, k = e.begin()->first, red = min(dis, t);
            e.erase(e.begin()); // begin 返回 set 中最小值的指针
            //erase 用来删除 set 的中某值或某指针的所在
            dis -= red, t -= red, sum -= red;
            cost += 1ll * k * red;
            if(t) e.insert({k, t}); // 这几行是跑路的过程，注意实现细节。 
        }
        int ine = 0; // 记录加多少
        while(lim != 0) {
            if(sum < m) {
                int add = min(lim, m - sum); // 油箱没满就加满
                lim -= add, sum += add;
                ine += add;
            }
            else {
                if(e.empty()) break; // 不然就用便宜油代替贵油
                int t = e.rbegin()->second, k = e.rbegin()->first, red = min(lim, t);
                if(k <= c) break; // rbegin == end - 1，即最大值
                e.erase(e.find(*e.rbegin()));
                // 这里先 find 再 erase 是为了只删一个，否则会删除某个值的所有所在
                t -= red, lim -= red;
                ine += red;
                if(t) e.insert({k, t});
            }
        }
        e.insert({c, ine}); // 必须只加一次，否则复杂度无保证
    }
    out(cost); en_;
}   
// 星間~ 干渉~ 融解~ 輪迴~ 邂逅~ 再生~ ララバイ~