NekoNowcoder

Appearance

硫酸钡之梦 - 题解 ​

标签与难度 ​

标签: 贪心, 数组, 思维题, 入门 难度: 900

题目大意喵~ ​

主人 sama，你好呀！这道题是关于一个叫做硫酸钡的小伙伴的梦，听起来就好有趣呢，喵~

事情是这样的：有 n 颗魔法糖果排成一排，第 i 颗的魔法值是 aia_i。我们可以从里面拿走一些糖果。但是，神仙沙有一个特别的要求：对于任何从 1 到 i 的前缀（也就是只看前 i 颗糖果），我们已经拿走的糖果数量和还没拿走的糖果数量，它们的差的绝对值不能超过 1。

我们的任务就是，在遵守这个规则的前提下，让我们拿到的所有糖果的魔法值总和最大！你能帮帮硫酸钡吗？呐，我们一起来想想办法吧！

输入：

  • 第一行是一个整数 nn，表示糖果的数量。
  • 第二行是 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n，表示每颗糖果的魔法值。

输出：

  • 一个整数，表示能获得的最大魔法值之和。

解题思路分析 ​

Meeeow~ 这道题的规则看起来有点绕，但只要我们像小猫咪一样，一步一步小心地往前走，就能发现其中的奥秘哦！

关键就在于这个神奇的限制条件：对于任意前缀 [1, i]，必须满足 |拿走的数量 - 没拿走的数量| <= 1。

我们来分析一下这个条件对我们的选择意味着什么吧！

  • 当 i = 1 时 (只看第1颗糖果):

    • 我们可以选择拿走它。这时，拿了1颗，没拿0颗。∣1−0∣=1≤1|1 - 0| = 1 \le 1。可以！
    • 我们也可以选择不拿。这时，拿了0颗，没拿1颗。∣0−1∣=1≤1|0 - 1| = 1 \le 1。也可以！
    • 看来第一步很自由呢，喵~

  • 当 i = 2 时 (看前2颗糖果):

    • 总共有2颗糖果。拿走的总数和没拿的总数加起来必须是2。
    • 比如，拿2颗，没拿0颗。∣2−0∣=2>1|2 - 0| = 2 > 1。不行！
    • 拿0颗，没拿2颗。∣0−2∣=2>1|0 - 2| = 2 > 1。不行！
    • 只能是拿1颗，没拿1颗。∣1−1∣=0≤1|1 - 1| = 0 \le 1。这才是唯一的选择！
    • 也就是说，在前两颗糖果中，我们必须拿走一颗、放弃一颗。为了让魔法值最大，我们当然应该拿走 max(a[1], a[2]) 啦！

  • 当 i = 3 时 (看前3颗糖果):

    • 总共有3颗糖果。拿走的总数和没拿的总数加起来是3。
    • 我们可以拿2颗，不拿1颗 (∣2−1∣=1|2-1|=1)，或者拿1颗，不拿2颗 (∣1−2∣=1|1-2|=1)。两种情况都满足条件。
    • 这取决于我们在第3颗糖果时怎么选。由于在 i=2 时我们已经拿了1颗、放弃了1颗，那么对于第3颗糖果，我们可以自由选择拿或者不拿。

  • 当 i = 4 时 (看前4颗糖果):

    • 和 i=2 的情况一样，总共有4颗糖果。
    • 唯一满足 |拿走的 - 没拿的| <= 1 的情况是拿2颗，没拿2颗。∣2−2∣=0≤1|2 - 2| = 0 \le 1。
    • 我们知道，在 i=2 的时候，我们拿了1颗、放弃1颗。现在要处理第3和第4颗糖果，为了最终达到“拿2颗，放弃2颗”的状态，我们必须在第3和第4颗糖果中，再拿走1颗、放弃1颗！
    • 那么，为了总魔法值最大，我们理所当然地应该在 a[3] 和 a[4] 中选择那个魔法值更大的来拿走，对吧？

发现了喵！规律出现啦！

这个规则把糖果们天然地分成了两两一组！

  • 对于 (a_1, a_2) 这一对，我们必须从中二选一。
  • 对于 (a_3, a_4) 这一对，我们也必须从中二选一。
  • ...
  • 对于 (a_{2k-1}, a_{2k}) 这一对，我们还是必须从中二选一！

这是因为在每个偶数位置 2k，我们都必须保证拿走的和没拿走的一样多，都是 k 个。这就意味着，从 2(k-1) 到 2k 这两步里，我们必须新拿一个，新放弃一个。

所以，我们的策略就变得非常简单了，这是一个经典的贪心思路：

  1. 把糖果两两分组：(a_1, a_2), (a_3, a_4), (a_5, a_6) ...
  2. 对于每一组，我们都选择其中魔法值较大的那一颗拿走。
  3. 把所有选出的糖果的魔法值加起来。

那如果 n 是奇数怎么办呢？ 比如说有5颗糖果。我们先按上面的方法处理前4颗：从 (a_1, a_2) 中选一个大的，从 (a_3, a_4) 中选一个大的。处理完这4颗后，我们总共拿了2颗，放弃了2颗。

现在轮到最后孤独的第5颗糖果 a_5 了。

  • 此时我们总共要考虑5颗糖果。
  • 如果我们拿走 a_5，总共就拿了3颗，放弃了2颗。∣3−2∣=1≤1|3 - 2| = 1 \le 1。完全符合规则！
  • 如果我们不拿 a_5，总共就拿了2颗，放弃了3颗。∣2−3∣=1≤1|2 - 3| = 1 \le 1。也符合规则。

为了让魔法值总和最大，我们当然应该选择拿走它啦！所以，如果 n 是奇数，最后一颗糖果我们直接拿走就好啦！

总结一下我们的无敌贪心策略：

  • 从头开始，两个两个地遍历糖果。
  • 每次遇到一对 (a_i, a_{i+1})，就把 max(a_i, a_{i+1}) 加入我们的总魔法值。
  • 如果最后剩下孤零零的一颗糖果（当 n 是奇数时），直接把它也加入总魔法值。

这样就能得到最优解了，是不是很简单呀，喵~

代码实现 ​

下面是我根据这个思路，为你精心准备的一份 C++ 代码，注释超详细的哦！

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

// 使用一个好听的函数名，让代码也充满魔法吧~
void solveMagicalCandies() {
    int n;
    std::cin >> n;
    
    // 用 vector 来存放糖果的魔法值，很方便喵~
    std::vector<long long> magicValues(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> magicValues[i];
    }
    
    long long maxSum = 0;
    
    // 我们以步长为 2 来遍历数组，这样正好可以两两分组
    // 循环条件 i < n - 1 保证了我们不会在只剩一个元素时还去访问 i+1
    for (int i = 0; i < n - 1; i += 2) {
        // 对于每一对 (magicValues[i], magicValues[i+1])
        // 我们贪心地选择魔法值更大的那一个
        maxSum += std::max(magicValues[i], magicValues[i+1]);
    }
    
    // 检查 n 是否为奇数。如果是，最后一个元素还没有被处理
    if (n % 2 != 0) {
        // 对于这最后一个孤独的糖果，我们直接拿走它！
        maxSum += magicValues[n - 1];
    }
    
    std::cout << maxSum << std::endl;
}

int main() {
    // 为了更快的输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    // 题目没有说有多组测试数据，但好习惯是写成可以处理多组的形式
    int t = 1;
    // std::cin >> t; // 如果有多组数据，就解开这行注释
    while (t--) {
        solveMagicalCandies();
    }
    
    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(N)O(N) 我们只需要从头到尾遍历一次糖果数组。循环的步长是2，所以大约执行了 N/2N/2 次操作。因此，总的时间复杂度和糖果数量 NN 是线性相关的，记作 O(N)O(N)。

  • 空间复杂度: O(N)O(N) 我们使用了一个 vector 来存储所有 NN 个糖果的魔法值。这是主要的额外空间开销。如果把输入数据所占空间不计入，那么我们只用了几个变量（如 n, maxSum, i），辅助空间复杂度就是 O(1)O(1)。

知识点总结 ​

这道题虽然包装在可爱的故事里，但核心是在考验我们的贪心算法思想和问题分析能力，喵~

  1. 约束条件分析: 解题的关键是正确理解 |拿走的 - 没拿的| <= 1 这个约束。通过分析小规模的例子（i=1, 2, 3, 4），我们能发现它强制在每个偶数长度的前缀上实现数量上的完美平衡。
  2. 贪心选择 (Greedy Choice): 识别出问题可以分解为一系列局部最优选择。在这里，局部最优就是“在每对糖果中选价值大的那个”。
  3. 局部最优到全局最优的证明: 我们需要确定局部最优选择能够导向全局最优解。在本题中，因为每个糖果对 (a_{2k-1}, a_{2k}) 的选择是独立的（无论之前怎么选，到 2k-2 时都是平衡的，所以 2k-1 和 2k 的选择只影响它们自己），所以局部最优的累加就是全局最优。
  4. 处理边界情况: 不要忘记处理 n 为奇数的情况！这是算法题中常见的“陷阱”，要像猫咪一样细心哦。

希望这篇题解能帮到你，主人 sama！如果还有其他问题，随时可以再来找我玩哦，喵~ >ω<