【算法日记 11】贪心思维的究极化简不要模拟直击本质 场景引入被“吓唬”的拿糖果游戏今天遇到了一道极其“唬人”的逻辑题游戏规则有NNN袋糖果。偶数个糖果的袋子归小蓝奇数个糖果的袋子归小桥。胜利条件小蓝可以随意对袋子重新排队。要求在拿糖果的任何时刻除了刚开始小蓝的总糖果数必须严格大于小桥。问是否能做到很多同学看到“重新排列”、“任何时刻”大脑瞬间开始疯狂模拟我是不是要把大的偶数放前面小的奇数放后面如果是交替放呢越想越复杂最后代码写成了一团乱麻。今天我们就来学习算法竞赛中极其重要的一种思维方式寻找最优的极端情况✨ 满级降维打击让小蓝“作弊”到底既然小蓝可以随意重新排列而且他希望自己的糖果永远比小桥多。那咱们干脆耍个流氓把所有属于小蓝的袋子偶数袋全部排在最前面把所有属于小桥的袋子奇数袋全部扔到最后面我们来看看这个极其“自私”的排队方式会发生什么前半场全是偶数小蓝疯狂拿糖果他的分数节节攀升而小桥只能干瞪眼分数为 0。小蓝绝对稳赢后半场全是奇数小蓝的袋子拿完了轮到小桥拿了。小桥的分数开始追赶。 灵魂拷问来了小桥在后半场疯狂追赶她什么时候会赢只有在最后所有的袋子都拿完时如果小桥的总糖果≥\ge≥小蓝的总糖果小桥才会反超因为题目要求**“在任何时刻”**小蓝都要赢所以哪怕是到了最后一个袋子拿完的时刻小蓝也必须赢。也就是说小蓝的糖果总和必须严格大于小桥的糖果总和只要偶数总和 奇数总和把偶数全放前面小蓝就绝对不可能输相反如果偶数总和 奇数总和那无论你前面怎么排列到了最后一步小蓝的总分一定会被追平或反超绝无胜算。 隐藏的“百亿级”数据炸弹逻辑理顺了我们只需要分别求出偶数的和、奇数的和比较一下大小就行了。连数组都不需要开连排序都不需要做但是出题人在这里埋了一个极其阴险的雷数据溢出Integer Overflow。假设有10510^5105个袋子每个袋子里有10910^9109个糖果。加起来的总和高达101410^{14}1014远远超过了int的极限2×1092 \times 10^92×109。如果你用int sum_even 0;来存总和加到一半就会变成诡异的负数导致判断完全错误正解必须使用long long 光速 AC 模板大道至简#includeiostreamusingnamespacestd;intmain(){// 竞赛必备读写极速引擎ios::sync_with_stdio(false);cin.tie(0);intn;if(!(cinn))return0;// 降维打击连数组都不用开直接边读边算// 防坑指南总和可能极大必须用 long long 保命longlongsum_even0;// 小蓝的总糖果longlongsum_odd0;// 小桥的总糖果for(inti0;in;i){longlonga;cina;if(a%20){sum_evena;// 偶数归小蓝}else{sum_odda;// 奇数归小桥}}// 最终审判只要小蓝的总资产比小桥多他就一定能赢if(sum_evensum_odd){coutYES\n;}else{coutNO\n;}return0;} 总结在算法题中如果遇到要求“某个条件始终成立”可以试着去构造一个**“最有利于该条件成立的极端场景”**。这道题看似是一道复杂的数组重排题其实只要看穿了“把偶数全放前面”的最优策略它就瞬间退化成了一道只有几行代码的求和比较题。代码的长度往往与思维的深度成反比