魔法商店 - 题解

标签与难度

标签: 贪心, 二分查找, 前缀和, 模运算, 大数处理难度: 1900

题目大意喵~

你好呀，指挥官！这道题是关于给小猫买小鱼干的，喵~ 我最喜欢小鱼干了！

事情是这样的：一家魔法商店里有 $n$ 种不同包装的小鱼干。第 $i$ 种包装里有 $a_i$ 条鱼干，售价是 $2^{i-1}$ 个猫猫币。这些包装有个特点，就是越贵的包装里的小鱼干数量不会越少，也就是说，如果 $i < j$ ，那么一定有 $a_i \le a_j$ 。

小蓝要连续 $q$ 天给他的猫咪买鱼干，第 $j$ 天需要至少 $b_j$ 条。每天商店只开一次，每种包装也只能买一包。

我们的任务是，对于每一天，计算出要凑够当天所需鱼干的最小花费。因为花费可能很大，所以结果要对 998244353 取模哦~

解题思路分析

喵哈哈，一看到 $2^{i-1}$ 这种价格，我的DNA就动了！这不就是二进制嘛！每一位代表一种包装，买或不买就是1或0。总价格就是所选包装价格的总和。为了让总价格最小，我们应该尽可能地让二进制表示下的高位为0，也就是说，要尽量不买价格昂贵的包装（即 i 较大的包装）。

这个发现是解决问题的关键哦！基于这个思想，一个非常棒的贪心策略就浮现啦。不过，直接从最便宜的开始买，买到够为止，可能会买多很多，造成浪费，不一定是最优的。比如需要10条鱼干，买 {a_1=5, a_2=6} 就够了，花了 $1+2=3$ 币。但如果无脑买，可能买了 {a_1=5, a_2=4, a_3=3}，花了 $1+2+4=7$ 币，虽然鱼干够了，但钱花多了。

所以，我们需要一个更聪明的策略。让我们来一起推导一下吧，喵~

核心贪心策略：迭代购买

我们换个角度思考。对于一个需求量为 $B$ 的任务，我们该如何决策呢？

我们的目标是凑齐至少 $B$ 条鱼干，同时花费最少。这个过程可以分解成一个迭代决策的过程。

假设我们当前还需要 needed_jerkies 条鱼干。

确定购买范围：我们首先要确定一个大致的购买范围。一个很自然的想法是，找到一个最小的索引 p，使得只购买 $1, 2, \dots, p$ 这些包装，鱼干数量就首次超过我们当前的需求 needed_jerkies。也就是 $\sum_{i=1}^{p} a_i \ge \text{needed\_jerkies}$ 。这意味着，任何最优的购买方案，其购买的包装索引最大也不会超过 p。为了快速找到 p，我们可以预处理 a 数组的前缀和 sum_a，然后用二分查找（lower_bound）就好啦！
分析盈余与决策：现在我们有了一个初步计划：买下 $1, \dots, p$ 号所有包装。这样我们得到的鱼干总数是 sum_a[p]。但我们只需要 needed_jerkies 条，所以我们有 surplus = sum_a[p] - needed_jerkies 的盈余。这么多盈余，说明我们可以反悔，不买其中一些包装！为了让花费最小，我们应该优先不买那些最便宜的包装，对吧？
锁定必买品：我们能反悔到什么程度呢？我们可以不买任何一个满足 $a_i \le \text{surplus}$ 的包装 i。因为 a 数组是单调不减的，所以满足这个条件的包装肯定是位于数组前面的一段，也就是索引从 $1$ 到某个 l 的所有包装。这个 l 也可以用二分查找（upper_bound）在 a 数组上快速找到。
做出决策：
- 对于索引在 l+1 到 p 之间的包装，它们的鱼干数量都大于 surplus。如果我们不买它们中的任何一个，那么就算把 $1, \dots, l$ 全买了，鱼干数量也可能不够。所以，一个稳妥又贪心的决策就是：我们下定决心，买下 l+1 到 p 的所有包装。
- 我们将这些包装的费用加到总花费里，然后从 needed_jerkies 中减去它们提供的鱼干数量。
迭代：完成一次决策后，我们更新了 needed_jerkies。现在问题变成了一个规模更小的子问题：用剩下的 $1, \dots, l$ 号包装，去满足新的、更小的 needed_jerkies。我们重复上述步骤 1-4，直到 needed_jerkies $\le 0$ 为止。

这个过程就像一层层剥洋葱，每次都先确定一个大概范围，然后精准地锁定这个范围内最贵的一部分作为“必买品”，再处理剩下的需求。喵~是不是很巧妙？

准备工作

为了让这个算法跑得飞快，我们需要做一些预处理：

鱼干前缀和 sum_a: sum_a[i] 表示第1到第i种包装的总鱼干数。由于 a_i 和 n 都很大，这个和可能会超过 long long 的范围，所以我们需要用 __int128 来存储，以防万一。
花费前缀和 sum_cost: sum_cost[i] 表示买下第1到第i种包装的总花费，即 $\sum_{j=1}^{i} 2^{j-1} = 2^i - 1$ 。这个可以在 $O(N)$ 时间内递推出来，记得每步都取模哦。

每次查询时，我们就用这个迭代的贪心策略，配合二分查找，就能高效地得到答案啦！

代码实现

这是我根据上面的思路，精心为你准备的代码哦~ 注释很详细，希望能帮到你，喵！

cpp

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

// 使用 long long 作为默认整数类型，方便处理大数据
using int64 = long long;

// 定义模数
const int MOD = 998244353;

// 解决 __int128 在某些环境下无法直接输出的问题
std::ostream& operator<<(std::ostream& os, __int128_t val) {
    if (val < 0) {
        os << "-";
        val = -val;
    }
    if (val == 0) {
        return os << "0";
    }
    std::string s = "";
    while (val > 0) {
        s += (val % 10) + '0';
        val /= 10;
    }
    std::reverse(s.begin(), s.end());
    return os << s;
}

int main() {
    // 优化C++的IO速度，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n; // 包装种类数
    int q; // 查询天数
    std::cin >> n >> q;

    // a[i] 存储第 i 种包装的鱼干数 (i 从 1 开始)
    std::vector<int64> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
    }

    // 预处理鱼干数量的前缀和
    // 使用 __int128 防止溢出，因为 a_i 的总和可能很大
    std::vector<__int128_t> sum_a(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        sum_a[i] = sum_a[i - 1] + a[i];
    }

    // 预处理花费的前缀和
    // sum_cost[i] = cost(1) + ... + cost(i) = (2^i - 1) mod MOD
    std::vector<int64> sum_cost(n + 1, 0);
    int64 power_of_2 = 1; // 代表 2^(i-1)
    for (int i = 1; i <= n; ++i) {
        sum_cost[i] = (sum_cost[i - 1] + power_of_2) % MOD;
        power_of_2 = (power_of_2 * 2) % MOD;
    }

    for (int k = 0; k < q; ++k) {
        int64 b; // 当天需要的鱼干数
        std::cin >> b;

        int64 total_cost = 0;
        __int128_t needed_jerkies = b;
        
        // 只要还需要鱼干，就继续我们的贪心策略
        while (needed_jerkies > 0) {
            // 1. 找到最小的 p，使得 sum_a[p] >= needed_jerkies
            // lower_bound 返回第一个不小于 needed_jerkies 的迭代器
            auto it_p = std::lower_bound(sum_a.begin() + 1, sum_a.end(), needed_jerkies);
            int p_idx = std::distance(sum_a.begin(), it_p);

            // 2. 计算盈余
            __int128_t surplus = sum_a[p_idx] - needed_jerkies;

            // 3. 找到最大的 l <= p_idx，使得 a[l] <= surplus
            // upper_bound 返回第一个大于 surplus 的迭代器
            // `a.begin() + p_idx + 1` 是因为我们只在 1..p_idx 范围内查找
            auto it_l = std::upper_bound(a.begin() + 1, a.begin() + p_idx + 1, surplus);
            int l_idx = std::distance(a.begin(), it_l) - 1;

            // 4. 决策：购买 l+1 到 p_idx 的所有包装
            // 计算这部分的花费：sum_cost[p] - sum_cost[l]
            int64 cost_to_add = (sum_cost[p_idx] - sum_cost[l_idx] + MOD) % MOD;
            total_cost = (total_cost + cost_to_add) % MOD;
            
            // 5. 更新还需要的鱼干数量
            // 减去我们刚刚决定购买的包装所提供的鱼干
            needed_jerkies -= (sum_a[p_idx] - sum_a[l_idx]);
        }

        std::cout << total_cost << "\n";
    }

    return 0;
}

复杂度分析

时间复杂度: $O(N + Q \cdot (\log N)^2)$
- 预处理 sum_a 和 sum_cost 需要 $O(N)$ 的时间。
- 对于每个查询 q，我们会进入一个 while 循环。在循环的每一步：
  - 我们用 lower_bound 在 sum_a 上查找 p，耗时 $O(\log N)$ 。
  - 我们用 upper_bound 在 a 的一个子段上查找 l，耗时 $O(\log N)$ 。
  - 循环的次数是多少呢？可以证明，每次迭代后，needed_jerkies 的值会大幅减小。新的 needed_jerkies 会小于 sum_a[l_idx-1]，这意味着下一次迭代的 p_idx 至多为 l_idx-1。所以 p_idx 的值下降得非常快，循环次数是 $O(\log N)$ 级别的。
- 因此，每个查询的总时间复杂度是 $O(\log N \cdot \log N)$ 。总时间复杂度就是 $O(N + Q \cdot (\log N)^2)$ ，完全可以通过哦！
空间复杂度: $O(N)$
- 我们主要使用了 a, sum_a, sum_cost 这三个数组来存储预处理的结果，它们的大小都和 n 成正比，所以空间复杂度是 $O(N)$ 。

知识点总结

这道题真是一次有趣的挑战呢，喵~ 它考察了我们好几个方面的能力：

贪心思想：问题的核心在于发现价格是 $2$ 的幂次，从而引导我们建立一个“尽量不买贵的”的贪心策略。正确的贪心策略是解决问题的钥匙！
二分查找：std::lower_bound 和 std::upper_bound 是C++ STL中的强大工具，它们能帮助我们高效地实现贪心策略中的查找步骤，是优化时间复杂度的关键。
前缀和：预处理前缀和是一种经典技巧，能将对区间的查询从 $O(N)$ 降到 $O(1)$ ，在这里我们用它来快速计算一段包装的总鱼干数和总花费。
大数处理：要注意题目给的数据范围，a_i 的和可能会非常大，超出 long long 的表示范围。这时候 __int128 就派上用场啦！
模块化思维：将一个复杂的问题（找到最小花费）分解成一系列更小的、相同的子问题，并通过迭代来解决，这是一种非常重要的解题思路，喵~

希望这篇题解能帮助你理解这道题的奥妙！继续加油哦，指挥官！有什么问题随时可以再来问我~ 喵~

魔法商店 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

核心贪心策略：迭代购买 ​

准备工作 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​