「联合省选 2020 B」卡牌游戏 题解

问题分析

这个问题要求通过合并卡牌操作获得最大总分。关键规则：

• 每次合并最左侧的连续若干张卡牌（至少 $2$ 张）
• 新卡牌放在序列最左端，分值为被合并卡牌分值之和
• 每次合并获得的分值加到总分中

算法思路

核心观察

通过分析游戏过程发现一个重要性质：

除了第一次操作外，每次操作获得的分数实际上就是当前前缀和，并且这个前缀和会继续参与后续的合并

设前缀和 $s_i = \sum_{k=1}^i a_k$，则：

• 第一次合并 $[1, i]$ 获得分数 $s_i$
• 后续合并时，之前合并产生的新卡牌会继续参与，相当于前缀和可以多次贡献

贪心策略

对于 $i$ 从 $2$ 到 $n$：

• 计算前缀和 $s = \sum_{k=1}^i a_k$
• 如果 $s > 0$，则将 $s$ 累加到答案中
• 否则跳过（负贡献会减少总分）

数学表达：

$$\text{ans} = \sum_{i=2}^n \max(0, \sum_{k=1}^i a_k) $$

代码实现分析

#include <bits/stdc++.h>
using namespace std;
long long ans, x, s, n;

int main() {
    cin >> n;
    for (long long i = 1; i <= n; i++) {
        cin >> x;
        s += x;                    // 计算前缀和
        if (s > 0 && i != 1)       // 跳过i=1的情况
            ans += s;              // 累加正的前缀和
    }
    cout << ans;
    return 0;
}

关键代码解释

1. 变量说明：

   • s：当前前缀和 $\sum_{k=1}^i a_k$
   • ans：累计总分
   • i：当前处理的卡牌索引

2. 核心逻辑：

   • 遍历每张卡牌，更新前缀和
   • 从第二张卡牌开始（i != 1），如果前缀和为正就累加

正确性证明

为什么这样贪心是正确的？

考虑最终的最优操作序列，可以证明：

1. 正的前缀和应该被利用：如果某个前缀和 $s_i > 0$，那么通过合适的操作顺序，这个值可以贡献到总分中
2. 负的前缀和应该避免：合并产生负分值的操作不如不进行
3. 操作顺序不影响结果：由于合并后的卡牌总是放在最左端，正的前缀和总能被后续操作利用

复杂度分析

• 时间复杂度：$O(n)$，只需一次线性扫描
• 空间复杂度：$O(1)$，仅使用常数个变量
• 最优性：该贪心策略能得到全局最优解

样例验证

样例1：[2, -1, 2]

• $i=2$：$s = 2 + (-1) = 1 > 0$，$ans = 1$
• $i=3$：$s = 1 + 2 = 3 > 0$，$ans = 1 + 3 = 4$ 输出：$4$ ✓

样例2：[-4, 3, 0, 7, -3, -5, -3]

• $i=2$：$s = -1$，跳过
• $i=3$：$s = -1$，跳过
• $i=4$：$s = 6 > 0$，$ans = 6$
• $i=5$：$s = 3 > 0$，$ans = 6 + 3 = 9$
• $i=6,7$：$s$ 为负，跳过 输出：$9$ ✓

算法标签

🏷️ 主要算法

贪心算法 - 通过局部最优选择达到全局最优

🏷️ 数学工具

前缀和 - 利用序列前缀性质简化计算 最优化 - 在操作约束下求最大得分

🏷️ 问题特征

序列操作优化 - 在特定操作规则下优化序列处理 决策优化 - 选择何时进行合并操作

🏷️ 复杂度类别

线性算法 - $O(n)$ 时间解决大规模数据

这个解决方案通过深入理解游戏机制，发现了问题的数学本质，用极其简洁的 $O(n)$ 贪心算法解决了看似复杂的问题。