1. 项目概述与问题拆解最近在刷JOIGST 2025的题目遇到了这道P13734“雪球2”。题目描述挺有意思的说的是有一排雪球你每次只能选择相邻的两个来合并而且合并有个苛刻的条件左边雪球的大小l和右边雪球的大小r必须满足0 ≤ l - r ≤ 1。换句话说要么l和r相等要么l只比r大1。你的目标是通过这样的操作看看能不能把所有雪球最终合成一个。这题的数据范围不小N最大能到50万A_i最大能到10的12次方直接暴力模拟或者搜索肯定没戏。乍一看有点像经典的“石子合并”或者“括号匹配”问题但多了这个差值限制就让整个问题的性质变得很不一样。我花了些时间研究发现这其实是一个关于“单调栈”和“贪心”的巧妙应用核心在于判断给定的序列能否被“完全消去”。下面我就把自己解题时的完整思路、代码实现以及踩过的几个坑详细分享一下特别适合正在准备信奥赛、对贪心和栈的应用感兴趣的同学。2. 核心思路与算法设计2.1 问题本质与初步观察首先我们得理解这个合并操作到底在干什么。题目要求最终只剩下一个雪球这意味着我们需要进行N-1次合并操作。每一次操作都会减少一个雪球并将两个相邻的雪球替换为它们的和。关键的限制条件是0 ≤ l - r ≤ 1。这可以拆解成两种情况l r两个雪球大小相等。l r 1左边雪球比右边雪球恰好大1。这个条件不是对称的。它只允许左边大于或等于右边且差值最多为1。这意味着从右向左看一个雪球只能和它左边那个比它小或相等的雪球合并因为如果它想作为l去合并右边的它自己必须更大或相等。这个方向性提示我们处理顺序可能很重要。一个最直接的暴力想法是模拟所有可能的合并顺序也就是搜索。但N最大50万搜索的空间是指数级的完全不可行。我们需要寻找规律。让我们从小例子开始手动模拟一下题目给的样例1[1, 1, 1, 1, 1]。 按照题解的操作先合并第4和第5个都是1得到[1,1,1,2]。此时序列是[1,1,1,2]。 接下来合并第1和第2个都是1得到[2,1,2]。 然后合并第1和第2个2和1满足2-11得到[3,2]。 最后合并第1和第2个3和2满足3-21得到[5]。 成功了。如果我们换一种合并顺序呢比如一开始就合并第1和第2个得到[2,1,1,1,1]。接下来你会发现有点棘手。[2,1]可以合并满足条件得到[3,1,1,1]。然后[3,1]的差是2不满足条件无法合并。我们只能尝试合并后面的[1,1]得到[3,2,1]。此时[3,2]差为1可以合并成[5,1]但最后的[5,1]差为4无法合并。这条路径就失败了。这说明合并顺序对最终结果有决定性影响。我们的算法必须能判断是否存在至少一种成功的合并顺序。2.2 关键转化栈模拟与“块”的概念这道题的一个经典解法是使用栈Stack来模拟从左到右的处理过程。为什么是栈我们可以把问题想象成“消化”这个序列。我们维护一个栈栈里的每个元素代表一个“雪球块”或者叫“合并后的雪球”。我们从左到右遍历原始的雪球数组A。对于当前遍历到的雪球a我们把它看作一个待处理的“新块”。现在我们需要尝试让它和栈顶的块也就是它左边的已处理块进行合并。但合并必须满足题目条件栈顶的块作为l新块a作为r需要满足0 ≤ l - a ≤ 1。如果满足条件我们就可以合并弹出栈顶l将la作为新的a一个新的待处理块。但是合并后的新块(la)可能又可以和新的栈顶块满足合并条件因为(la)变大了可能比新的栈顶块大1或者相等。因此我们需要循环检查直到栈为空或者当前块a无法再与栈顶合并为止。最后将处理完的当前块a压入栈中。这个过程的直觉是我们总是试图让当前元素“吃掉”它左边可以吃的所有东西把自己养大然后再入栈等待右边的元素来“吃”它或者被它吃。遍历完整个数组后我们检查栈的情况如果栈中只剩下一个元素说明整个序列被成功合并成了一个块输出Yes。否则输出No。但是这里有一个巨大的陷阱这个贪心策略是否正确我们来看一个反例序列[2, 1, 1]。 按照上述算法栈为空a2入栈。栈[2]读入a1。栈顶l2l-a1满足条件。合并弹出2新a3。栈为空将3入栈。栈[3]读入a1。栈顶l3l-a2不满足条件。将1入栈。栈[3, 1]遍历结束栈中有两个元素算法输出No。然而这个序列真的无法合并吗我们手动试试先合并后两个[1,1]相等满足条件得到[2,2]。再合并[2,2]相等满足条件得到[4]。成功了这说明我们简单的从左到右“贪心吃”的策略是错的。问题出在哪里在于我们让2过早地吃掉了右边的1变成了3这个3挡住了后面[1,1]自己合并成2的可能性。正确的策略应该是当2看到右边的1时它应该“等一等”让后面的[1,1]先合并成2然后[2,2]再合并。这引出了正确的核心思想我们不应该只比较当前块和栈顶块而应该比较栈顶块和“未来可能生成的最小块”。换句话说我们需要保证栈内的块大小是非递减的并且任意相邻两块的大小差不能超过1实际上在最终成功的序列里栈内应该是一个严格递增的序列除了最后可能允许一个特殊情况。2.3 正确算法维护单调栈与“合并时机”正确的算法基于以下观察为了最终能合并成一个整个序列必须能够被划分成若干个“段”每个段内部可以独立合并成一个“块”并且这些“块”的大小从左到右是单调不减的。更严格地说在合并过程中栈中保存的应该是这些“块”并且它们的大小应该是严格递增的。为什么因为如果栈里有两个块x, y且x y那么当y想要作为l去合并后面的块时它至少要和后面的块r满足y - r 1。如果x比y小那么x永远没有机会再去合并后面的东西了因为后面的块如果要被合并也是先被y考虑所以x必须在此之前被合并掉。因此成功合并的栈状态应该是一个递增序列。算法步骤修正如下初始化一个空栈stk。从左到右遍历每个雪球a a. 将a作为当前待处理的值。 b.关键循环只要栈非空并且栈顶元素当前值a注意这里是小于等于我们就尝试合并。但合并需要满足精确条件stack.top() - a 1 stack.top() - a 0即0 ≤ stack.top() - a ≤ 1。如果满足则弹出栈顶top更新a top a。然后继续用新的a与新的栈顶比较。 c. 循环结束后将当前的a压入栈中。遍历结束后检查栈的大小。如果栈的大小为1输出Yes否则输出No。这个算法和之前错误算法的区别在于循环条件不再是“当前a可以吃栈顶就吃”而是“只要栈顶不大于当前a就看看能不能吃”。如果栈顶比当前a大很多我们就停下来把a入栈。这保证了栈内元素的单调性从栈底到栈顶递增。让我们用这个正确算法再过一遍反例[2,1,1]栈空a2入栈。栈[2]读a1。栈顶2 1不进入循环因为栈顶2大于a1。直接将1入栈。栈[2, 1]。注意此时栈不是递增的这暗示了可能有问题但算法还没结束。读a1。栈顶是1a1。栈顶1 a(1)进入循环。检查条件1-10满足。弹出栈顶1a112。循环继续新的栈顶是2a2。栈顶2 a(2)检查条件2-20满足。弹出栈顶2a224。栈空循环结束。将a4入栈。栈[4]遍历结束栈大小为1输出Yes。正确这个算法成功的关键在于它让后面来的1和栈顶的1先合并成了2然后这个2才去和更早的2合并。它通过“栈顶不大于当前值”这个条件延迟了合并的决策给了后面元素先“抱团”的机会。注意这里有一个非常细微但至关重要的点。循环条件是while (!stk.empty() stk.top() a)。为什么是而不是考虑序列[1,1]。第一个1入栈第二个a1时栈顶1a成立进入循环检查1-10可以合并最终得到[2]。如果条件是就不会进入循环两个1会都留在栈里导致误判。所以是保证相等元素能够合并的关键。3. 算法实现与代码详解理解了算法思想我们来看C实现。这道题的数据范围要求算法时间复杂度在O(N)级别空间复杂度O(N)。我们的栈模拟算法正好满足。3.1 数据结构选择与输入输出首先N最大5e5A_i最大1e12合并过程中数值可能超过int范围必须使用long long类型。栈我们直接用C STL的std::stack。输入输出量不大但为了保险可以使用scanf/printf或者关闭同步流的cin/cout。#include iostream #include vector #include stack using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin N; vectorll A(N); for (int i 0; i N; i) { cin A[i]; } // ... 核心算法部分 return 0; }3.2 核心算法实现接下来是实现核心的栈模拟逻辑。我们需要严格按照上一节描述的步骤来写。stackll stk; for (int i 0; i N; i) { ll cur A[i]; // 当前待处理的雪球大小 // 只要栈非空且栈顶元素不大于当前值就尝试合并 while (!stk.empty() stk.top() cur) { ll top_val stk.top(); // 检查合并条件0 top_val - cur 1 if (top_val - cur 0 top_val - cur 1) { // 可以合并 stk.pop(); cur top_val cur; // 合并后的大小 } else { // 不能合并跳出循环 break; } } // 将处理后的当前值压入栈中 stk.push(cur); }3.3 完整代码与测试将以上部分组合起来并加上结果判断就得到了完整代码。我们多用几个例子测试一下。#include iostream #include vector #include stack using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin N; vectorll A(N); for (int i 0; i N; i) { cin A[i]; } stackll stk; for (int i 0; i N; i) { ll cur A[i]; // 尝试与栈顶合并 while (!stk.empty() stk.top() cur) { ll top_val stk.top(); // 判断是否满足合并条件栈顶比cur大0或1 if (top_val - cur 0 top_val - cur 1) { stk.pop(); cur top_val cur; // 合并 } else { // 不满足条件停止合并尝试 break; } } stk.push(cur); } // 判断最终栈内是否只剩一个元素 if (stk.size() 1) { cout Yes\n; } else { cout No\n; } return 0; }测试样例样例15\n1 1 1 1 1- 输出Yes。样例2题目未给出具体值但应输出No我们可以构造一个[2, 1]。输入2\n2 1- 输出No。因为栈顶2比当前1大不进入循环直接入栈最后栈大小为2。反例[2,1,1]输入3\n2 1 1- 输出Yes。复杂例子[1,2,1,1]手动模拟一下。算法会输出No。你可以试试看是否正确。3.4 算法正确性简要证明与复杂度分析正确性这个算法的核心在于维护了一个“单调栈”实际上是单调不减栈但通过合并操作最终有效部分趋向于递增。它确保了在任意时刻栈中的每个元素块都是“已合并的、不能再与左边元素合并”的状态。而算法尝试合并的条件栈顶 当前值且 差值1实际上是在模拟唯一可行的成功合并顺序即总是让小的、相等的、或稍大的右边块去吸收或与左边块合并。可以证明如果存在一种合并顺序能合成一个大雪球那么这个算法一定能找到即最终栈大小为1反之如果算法最终栈大小不为1那么任何合并顺序都不可能成功。这是一个典型的贪心算法其正确性基于“决策包容性”和“无后效性”的论证。时间复杂度每个元素最多入栈一次、出栈一次while循环的总次数是O(N)的因此整体时间复杂度是O(N)完美处理N5e5的数据。空间复杂度主要是栈的空间最坏情况O(N)。4. 常见问题与调试技巧在实际实现和调试这道题时我遇到了几个典型问题这里列出来供大家参考。4.1 整数溢出问题这是最容易忽略也最致命的问题。A_i最大1e12合并操作是加法。在最坏情况下如果所有雪球都能合并最终那个大雪球的大小是sum(A_i)这个值最大可能是5e5 * 1e12 5e17这远远超过了int约21亿甚至long在Windows 64位编译器上通常也是4字节的范围。必须使用long long64位整数范围约±9e18。在C中写typedef long long ll是个好习惯。注意有些编译器环境下long可能是64位的但为了跨平台安全竞赛中一律用long long是最稳妥的。输入输出时也要对应使用%lld如果用scanf/printf或直接使用cin/cout。4.2 合并条件判断的细节合并条件0 ≤ l - r ≤ 1在代码中要小心实现。我见过一些错误的写法if (l r l - r 1)这是正确的逻辑等价。if (l r || l r 1)这也是正确的并且更直观。错误写法if (abs(l - r) 1)。这会把r比l大1的情况也包括进来例如l1, r2差为1但l-r-1不满足0 ≤ l-r。题目要求必须是左边大于等于右边不能右边大于左边。在我的代码中我使用了if (top_val - cur 0 top_val - cur 1)清晰表达了0 ≤ diff ≤ 1。4.3 循环条件的理解与陷阱while (!stk.empty() stk.top() cur)这个条件至关重要。stk.top() cur这意味着栈顶块不大于当前块。如果栈顶块比当前块大很多比如栈顶是100当前是1我们就不尝试合并因为当前块1不可能“吃掉”左边的100不满足差值≤1的条件。同时让1入栈等待后面可能来的1或2和它先合并。如果改成stk.top() cur算法就退化成最初那个错误的“贪心吃”版本。如果去掉这个条件只判断是否满足合并条件那么对于栈顶比当前值大的情况也会不断尝试判断虽然会因为条件不满足而立刻break但逻辑上不清晰而且对于某些边界情况可能处理有误。4.4 调试与测试用例构造自己构造测试用例是验证算法正确性的好方法。可以从简单到复杂基础用例[1,1]-Yes[2,1]-No左边比右边大1以上无法启动合并[1,2]-No左边小于右边不满足条件小规模组合[1,1,1]-Yes(1,1)合并成2再和1合并等等2和1差1可以合并成3。或者1和(1,1)合并成的2再合并需要算法验证[2,1,1]-Yes我们的反例用于测试算法是否纠正[1,2,1]-?手动模拟一下似乎不行。算法应该输出No。单调序列[1,2,3,4]-No递增序列左边总是小于右边无法合并[4,3,2,1]-No递减序列但差值可能大于1且合并方向受限[1,1,2,2,3,3]-?可以自己推导一下。随机大数据可以用小数据暴力搜索DFS枚举所有合并顺序来验证你的算法是否正确。对于N8的数据暴力搜索是可行的可以用来对拍。4.5 性能优化与代码风格对于这道题O(N)算法已经足够快。代码风格上注意使用ios::sync_with_stdio(false); cin.tie(nullptr);来加速C的输入输出这在处理大量数据时很必要。变量名要有意义比如cur表示当前值stk表示栈。关键步骤加上注释尤其是while循环的条件和合并条件方便自己回顾和他人阅读。5. 算法扩展与相关题目这道“雪球2”的本质是一个“栈模拟贪心”问题它考察的是对操作顺序的推理和用栈维护局部可合并性的能力。类似思路的题目还有不少比如括号匹配栈的经典应用判断括号序列是否合法。行星碰撞LeetCode 735行星有大小和方向正向右负向左相遇时小的爆炸一样大则都爆炸。也可以用栈来模拟。移掉K位数字LeetCode 402给定数字字符串移除k位使其最小。维护一个单调递增栈。函数的独占时间LeetCode 636模拟函数调用栈。理解这类问题的共性它们都涉及顺序处理元素并且当前元素的处理结果可能会影响之前元素的状态通常是栈顶元素。解决问题的关键在于找到那个“栈顶元素与当前元素的关系条件”以及何时进行“合并”或“消除”操作。回到这道题如果你能独立想到这个栈模拟的解法并且清晰地理解while循环里那个条件的内涵那么你对贪心和栈的理解就已经相当不错了。信奥赛和很多算法竞赛中这类题目往往代码不长但思维难度不小需要多练习和总结。