KabaleoLite - 题解

标签与难度

标签: 贪心, 前缀和, 前缀最值, 思维题, 贡献法, 喵~ 难度: 1800

题目大意喵~

你好呀，指挥官！阿波罗开了一家快餐店，名叫 "Kabaleo Lite"，真是个好听的名字呐！

店里有 $n$ 种食物，编号从 1 到 $n$ 。第 $i$ 种食物的利润是 $a_i$ （可能是负数哦，因为食材可能很贵！），库存是 $b_i$ 份。

这家店的点餐规则很特别的说：

每位客人至少会得到一份食物。
每位客人收到的食物，必须是从 1 号食物开始的连续几种，比如 (1), (1, 2), (1, 2, 3) 这样。每种食物都只会给一份。我们把这样一个组合称为一个“套餐”好了，喵~

现在，阿波罗想知道，他最多能招待多少位客人？并且，在招待最多客人的前提下，他能获得的最大总利润是多少呢？

输入输出

输入: 多组测试数据。每组数据先是食物种类数 $n$ ，然后是两行，分别是 $n$ 个食物的利润 $a_1, \dots, a_n$ 和库存 $b_1, \dots, b_n$ 。
输出: 对于每组数据，输出一行 "Case #k: V P"，其中 k 是测试数据编号，V 是最大访客数，P 是对应的最大利润。

解题思路分析

这道题有两个目标：先最大化客人数量，再最大化利润。我们一步一步来分析，喵~

第一步：如何最大化客人数量？

规则里最关键的一条是：每位客人收到的套餐，都必须从 1 号食物开始。这意味着，每一位被招待的客人，都必须消耗一份 1 号食物！

我们有多少份 1 号食物呢？有 $b_1$ 份。所以，无论我们怎么组合套餐，最多也只能招待 $b_1$ 位客人，因为 1 号食物会最先被用完。

那么，我们能招待满 $b_1$ 位客人吗？当然可以啦！最简单的方法就是，给这 $b_1$ 位客人每人只发一份 1 号食物。这完全符合规则，对吧？

所以，第一个问题的答案非常简单：最大客人数量就是 $b_1$ ，喵~

第二步：如何为这 $b_1$ 位客人实现最大利润？

好戏现在才开始！我们已经确定了要招待 $b_1$ 位客人。现在的问题是，怎么给他们分配套餐，才能让总利润最高呢？

一个很自然的想法是：我们有 $b_1$ 次招待机会，每一次都应该选择当前库存允许的、并且利润最高的套餐。

举个栗子：假设套餐 (1, 2) 的利润比套餐 (1, 2, 3) 高，而套餐 (1) 的利润最低。那我们每次都应该优先发 (1, 2) 套餐，直到 1 号或 2 号食物库存不足，再考虑其他的。

这个模拟的想法是对的，但 $b_1$ 可能非常大（比如 $10^9$ ），一个一个客人地模拟肯定会超时的说。我的猫爪都得按冒烟了！(>ω<)

所以，我们需要一种更快的、更宏观的计算方法。

换个角度看问题

我们不要一个一个地看客人，而是从“限制”的角度出发。

一个客人能拿到 (1, ..., k) 套餐，必须保证 $1, 2, \dots, k$ 号食物都还有库存。
也就是说，能拿到至少包含到第 $k$ 号食物的套餐的客人总数，受限于 $b_1, b_2, \dots, b_k$ 中最少的那一个。

我们来定义几个有用的“魔法道具”：

套餐利润 P_k: 表示 (1, ..., k) 这个套餐的总利润。很容易用前缀和求出： $P_k = \sum_{i=1}^{k} a_i$
库存瓶颈 m_k: 表示最多有多少位客人可以拿到尺寸不小于 $k$ 的套餐（即包含 $1, \dots, k$ ）。这个瓶颈由 $1$ 到 $k$ 的食物中库存最少的那种决定。所以 m_k 也是一个前缀最小值： $m_k = \min(b_1, b_2, \dots, b_k)$ 注意哦， $m_1 \ge m_2 \ge \dots \ge m_n$ 。

贡献法闪亮登场！

现在，我们可以把 $b_1$ 位客人进行分组！

有多少客人，他们能拿到的套餐尺寸最大就是 $k$ 呢？
- 这意味着他们可以拿到尺寸为 $k$ 的套餐，但拿不到尺寸为 $k+1$ 的套餐。
- 能拿到尺寸不小于 $k$ 的客人有 $m_k$ 位。
- 能拿到尺寸不小于 $k+1$ 的客人有 $m_{k+1}$ 位。
- 所以，因为库存限制，最多只能拿到尺寸 $k$ 套餐的客人数量就是 $m_k - m_{k+1}$ 位！（我们定义 $m_{n+1}=0$ ）
对于这 $m_k - m_{k+1}$ 位客人，他们能选择的套餐是 (1), (1,2), ..., (1,...,k)。为了最大化利润，我们肯定会给他们这 $k$ 种套餐里利润最高的那一个！

我们再来定义一个魔法道具： 3. 最优套餐利润 P*_k: 表示在尺寸不超过 $k$ 的所有套餐中，能获得的最大利润。 $$ P^*_k = \max(P_1, P_2, \dots, P_k) $$ 这个也可以通过一次遍历来预处理出来。

现在，总利润的计算就清晰多啦！

有 $m_1 - m_2$ 位客人，他们最多只能拿到尺寸为 1 的套餐，他们贡献的利润是 $(m_1 - m_2) \times P^*_1$ 。
有 $m_2 - m_3$ 位客人，他们最多只能拿到尺寸为 2 的套餐，他们贡献的利润是 $(m_2 - m_3) \times P^*_2$ 。
...
有 $m_k - m_{k+1}$ 位客人，他们最多只能拿到尺寸为 $k$ 的套餐，他们贡献的利润是 $(m_k - m_{k+1}) \times P^*_k$ 。
...
有 $m_n - m_{n+1} = m_n$ 位客人，他们最多能拿到尺寸为 $n$ 的套餐，他们贡献的利润是 $m_n \times P^*_n$ 。

把这些全部加起来，就是我们能获得的最大总利润！

\text{Total Profit} = \sum_{k=1}^{n} (m_k - m_{k+1}) \times P^*_k

算法总结

整个算法流程就像猫咪散步一样优雅~

最大访客数: 就是 b[1]。
最大利润: a. 计算利润 a 的前缀和数组 P。 b. 计算库存 b 的前缀最小值数组 m。 c. 计算 P 数组的前缀最大值数组 P*。 d. 根据公式 $\sum_{k=1}^{n} (m_k - m_{k+1}) \times P^*_k$ 计算总利润。

这个算法只需要几次线性扫描，时间复杂度是 $O(N)$ ，空间复杂度是 $O(N)$ ，非常高效，完全不会超时啦！

代码实现

这是我根据上面的思路，精心为你准备的代码，喵~ 注释超详细的哦！

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// 为了防止总利润过大，我们使用 __int128 来存储，它比 long long 更大
// 如果题目数据范围没那么夸张，用 long long 也是可以的
using int128 = __int128;

// 一个辅助函数，用来打印 __int128 类型的数字
void print_int128(int128 n) {
    if (n == 0) {
        std::cout << "0";
        return;
    }
    if (n < 0) {
        std::cout << "-";
        n = -n;
    }
    std::string s = "";
    while (n > 0) {
        s += (n % 10) + '0';
        n /= 10;
    }
    std::reverse(s.begin(), s.end());
    std::cout << s;
}

void solve(int case_num) {
    int n;
    std::cin >> n;
    std::vector<long long> a(n); // 利润
    std::vector<long long> b(n); // 库存

    for (int i = 0; i < n; ++i) std::cin >> a[i];
    for (int i = 0; i < n; ++i) std::cin >> b[i];

    // --- 第一步：最大访客数 ---
    // 任何客人都需要1号食物，所以最大访客数就是1号食物的库存
    long long max_visitors = (n > 0) ? b[0] : 0;

    // --- 第二步：最大利润 ---
    if (n == 0) {
        std::cout << "Case #" << case_num << ": 0 0\n";
        return;
    }

    // 1. 计算利润的前缀和 P_k
    std::vector<long long> prefix_sum_profits(n);
    prefix_sum_profits[0] = a[0];
    for (int i = 1; i < n; ++i) {
        prefix_sum_profits[i] = prefix_sum_profits[i - 1] + a[i];
    }

    // 2. 计算库存的前缀最小值 m_k
    std::vector<long long> prefix_min_stocks(n);
    prefix_min_stocks[0] = b[0];
    for (int i = 1; i < n; ++i) {
        prefix_min_stocks[i] = std::min(prefix_min_stocks[i - 1], b[i]);
    }

    // 3. 计算 P_k 的前缀最大值 P*_k
    std::vector<long long> max_profit_packages(n);
    max_profit_packages[0] = prefix_sum_profits[0];
    for (int i = 1; i < n; ++i) {
        max_profit_packages[i] = std::max(max_profit_packages[i - 1], prefix_sum_profits[i]);
    }

    // 4. 计算总利润
    int128 total_profit = 0;
    for (int k = 0; k < n; ++k) {
        long long m_k = prefix_min_stocks[k];
        // 如果 k 是最后一个食物，那么 m_{k+1} 就当做是 0
        long long m_k_plus_1 = (k + 1 < n) ? prefix_min_stocks[k + 1] : 0;
        
        // 这是最多只能拿到 k 号套餐的客人数
        long long num_visitors_in_group = m_k - m_k_plus_1;
        
        if (num_visitors_in_group > 0) {
            total_profit += (int128)num_visitors_in_group * max_profit_packages[k];
        }
    }

    std::cout << "Case #" << case_num << ": " << max_visitors << " ";
    print_int128(total_profit);
    std::cout << "\n";
}

int main() {
    // 加速输入输出，让程序跑得更快，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve(i);
    }

    return 0;
}

复杂度分析

时间复杂度: $O(N)$ 我们对输入的 a 和 b 数组进行了几次线性的遍历来计算前缀和、前缀最小值、前缀最大值，以及最后计算总利润。每次遍历都是 $O(N)$ 的，所以总的时间复杂度是 $O(N)$ ，非常快！
空间复杂度: $O(N)$ 我们使用了几个辅助数组 prefix_sum_profits, prefix_min_stocks, max_profit_packages 来存储中间结果，它们的大小都和输入的 $N$ 成正比，所以空间复杂度是 $O(N)$ 。

知识点总结

这道题真有趣，不是吗？它教会了我们：

抓住问题核心: 解决复杂问题时，先找到最关键的限制条件（比如这里的“每位客人都需要1号食物”），往往能让问题大大简化。
前缀和/最值的威力: 预处理前缀信息是一种非常强大的技巧，能把很多需要重复计算的问题优化到线性时间。
贡献法/转换视角: 当直接模拟或计算行不通时，试着从另一个角度看问题。把“为每个客人选套餐”转换成“计算每种套餐被选了多少次”，或者像我们最终做的，计算“每一组受同样限制的客人贡献了多少利润”，这就是贡献法的思想。
注意数据范围: 看到利润和库存都可能很大时，要想到累加的结果可能会超出 long long 的范围，这时候就需要 __int128 这样的“大杀器”啦，喵~

希望这篇题解能帮到你！如果还有不明白的地方，随时可以来问我哦！加油，你一定可以的！(ฅ'ω'ฅ)

KabaleoLite - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

第一步：如何最大化客人数量？ ​

第二步：如何为这 b1b_1b1​ 位客人实现最大利润？ ​

换个角度看问题 ​

贡献法闪亮登场！ ​

算法总结 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​