CF1238G. Adilbek and the Watering System

发表于 | 阅读数

有一个容量为$c$的水箱，初始是$c0$.

每时刻会掉$1ml$滴水。

有$n$个人，在$t_i$时刻来，最多带来$a_i$水，每毫升$b_i$元。

要让水箱可以坚持到$m$时刻。

求最小花费。

贪心。。。。

很妙。显然当要用到水的时候再用水，并且用价格最少的。

假设先把水都放进去，不管容量。每次发现要用水的时候，从里面取出最小的即可。

  • 如果我取出来，导致之前本来可以过的过不去呢？放心每次过需要水的时候按时间计算了。

如果考虑容量，如果我装满了，并且发现我的水多余了，那我可以取代那些预准备费用大于他的水。

用

1
map<int,int>q;

$q[x]$表示价格为$x$的水在准备区有多少。

一些小细节注意

  • 初始化准备区的水，以及$q[0]$。
  • 每次需要用水，准备区里的水需要减。
  • 水溢出需要的细节

弹出准备区的水复杂度最多$O(n\log n)$

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71


#include <bits/stdc++.h>

using namespace std;

#define ll int64_t

ll solve()
{
    int n, m, c, c0;
    cin >> n >> m >> c >> c0;
    vector<array<int, 3>> tmp(n + 2);
    for (int i = 1; i <= n; i++)
    {
        cin >> tmp[i][0] >> tmp[i][1] >> tmp[i][2];
    }
    tmp[n + 1] = {m, 0, 0};
    sort(tmp.begin(), tmp.end());
    map<int, ll> q;
    ll ans = 0;
    int now = c0;
    q[0] = c0;
    for (int i = 1; i < tmp.size(); i++)
    {
        auto [t, A, b] = tmp[i];
        int del = t - tmp[i - 1][0];
        if (del > c)
            return -1;
        while (!q.empty() && del > 0)
        {
            int w = min(q.begin()->second, 1ll * del);
            q.begin()->second -= w, del -= w, now -= w;
            ans += 1ll * w * q.begin()->first;
            if (q.begin()->second == 0)
                q.erase(q.begin());
        }
        if (del)
            return -1;
        int add = min(c - now, A);
        now += add;
        while (!q.empty() && A - add > 0 && b < q.rbegin()->first)
        {
            auto it = q.rbegin();
            if (A - add >= it->second)
            {
                add += it->second;
                q.erase(--q.end());
            }
            else
            {
                it->second -= A - add;
                add = A;
            }
        }
        q[b] += add;
        // cout << ans << endl;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--)
    {
        cout << solve() << endl;
    }
}