[蓝桥杯 2021 国 C] 巧克力

题意

有很多种巧克力，第 i 种有：

单价 $a_i$
保质期 $b_i$
数量 $c_i$

小蓝每天要吃一块，而且只能吃没有过期的巧克力。

问最少花多少钱，才能保证自己吃满 x 天。

思路

先看一个可以直接验证想法的朴素解：

cpp

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#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll INF = (1LL << 60);

int x, n;
ll price_[15], expire_[15];
int cnt_[15];
map<vector<int>, ll> memo;

// day 表示当前要给第 day 天选巧克力。
ll dfs(int day, vector<int> cnt) {
    if (day == 0) {
        return 0;
    }

    vector<int> key;
    key.push_back(day);
    for (int v : cnt) {
        key.push_back(v);
    }
    map<vector<int>, ll>::iterator it = memo.find(key);
    if (it != memo.end()) {
        return it->second;
    }

    ll ans = INF;
    for (int i = 0; i < n; i++) {
        if (cnt[i] == 0) {
            continue;
        }
        if (expire_[i] < day) {
            continue;
        }
        cnt[i]--;
        ll sub = dfs(day - 1, cnt);
        cnt[i]++;
        if (sub != INF) {
            ans = min(ans, sub + price_[i]);
        }
    }

    memo[key] = ans;
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> x >> n;
    for (int i = 0; i < n; i++) {
        cin >> price_[i] >> expire_[i] >> cnt_[i];
    }

    vector<int> cnt(cnt_, cnt_ + n);
    memo.clear();
    ll ans = dfs(x, cnt);
    if (ans == INF) {
        cout << -1 << '\n';
    }
    else {
        cout << ans << '\n';
    }
    return 0;
}

暴力想法是：第 day 天枚举吃哪一种还没过期、还有库存的巧克力。

这样虽然能做小数据，但显然不能处理 $10^5$ 级别的数据。

关键观察是：

如果我们倒着考虑“第 x 天、第 $x-1$ 天……第 1 天吃什么”
那么对于第 day 天来说，所有 $\text{保质期} \geqslant day$ 的巧克力都可以候选

而且为了总花费最小，这一天一定应该从这些候选里挑最便宜的那一种。

所以贪心策略就是：

按保质期从大到小排序
倒着枚举每一天 $day = x, x-1, \dots, 1$
把所有 $\text{保质期} \geqslant day$ 的巧克力加入小根堆
从小根堆里取一块当前最便宜的巧克力来吃

如果某一天堆空了，说明再怎么选也凑不满 x 天，答案就是 -1。

这里堆里需要记录：

单价
当前还剩多少块

每次取出后把数量减一，若还有剩余，就再放回堆里。

代码

cpp

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
72
73#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100005;

struct Choco {
    ll price;
    ll cnt;
    ll expire;
};

struct Node {
    ll price;
    ll cnt;

    bool operator < (const Node &other) const {
        return price > other.price;
    }
};

int x, n;
Choco a[MAXN];

bool cmp_expire_desc(const Choco &lhs, const Choco &rhs) {
    return lhs.expire > rhs.expire;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> x >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].price >> a[i].expire >> a[i].cnt;
    }

    sort(a + 1, a + n + 1, cmp_expire_desc);

    priority_queue<Node> pq;
    int ptr = 1;
    ll ans = 0;

    // 倒着考虑第 day 天要吃什么。
    // 这样 expiry >= day 的巧克力都可以用在这一天。
    for (int day = x; day >= 1; day--) {
        while (ptr <= n && a[ptr].expire >= day) {
            pq.push({a[ptr].price, a[ptr].cnt});
            ptr++;
        }

        while (!pq.empty() && pq.top().cnt == 0) {
            pq.pop();
        }

        if (pq.empty()) {
            cout << -1 << '\n';
            return 0;
        }

        Node cur = pq.top();
        pq.pop();
        ans += cur.price;
        cur.cnt--;
        if (cur.cnt > 0) {
            pq.push(cur);
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

排序复杂度 $O(n log n)$ 。

每一天最多做若干次堆操作，总复杂度 $O((n + x) \log n)$ 。

空间复杂度 $O(n)$ 。

总结

这题的核心不是“每天正着买”，而是“从最后一天倒着安排”。

倒着看之后，保质期条件就变成了简单的：

$expire \geqslant day$

然后每天从当前还能吃的巧克力里选最便宜的，就是很自然的小根堆贪心。

[蓝桥杯 2021 国 C] 巧克力

目录

题意

思路

代码

复杂度

总结