基本信息项目内容题目编号、来源P1031 均分纸牌 / NOIP 2002 提高组第一题训练层级A 贪心模板题知识版块贪心算法 / 线性递推 / 相邻交换模型解题前・关键信号识别维度分析目标、约束、底层结构目标线性排列的纸牌堆均分求最少移动次数约束只能向相邻堆移动纸牌一次移动任意张数计为 1 次操作底层结构线性局部最优递推从左到右逐堆处理多余 / 缺失的纸牌全部转移给右侧相邻堆。数据规模n ≤ 100单堆纸牌数 ≤ 10000数值范围小int 类型足够存储标准贪心为最优复杂度。候选算法和依据线性贪心递推依据线性排列下第 i 堆的差值只能通过第 i1 堆补齐不存在更优的跨堆移动方案局部最优可推导全局最优是该类问题的标准解法。复杂度预判O(n)仅需一次线性遍历即可完成计算空间复杂度 O(n)存储纸牌堆数组。解题后・外化复盘从会一次到稳定会维度内容实现结构 / 核心思路第一步计算所有纸牌的平均值即每堆最终的目标数量第二步从左到右遍历前 n-1 堆第三步若当前堆纸牌数不等于平均值则将差值转移给右侧相邻堆移动次数加 1遍历完成后最后一堆会自动等于平均值无需额外处理。一开始没有思路后来想到第一堆只能从第二堆获得到第二堆时因为第一堆已经满足条件所以不能动只能在第三堆上面操作所以直接从左到右依次操作就可以错因回溯逻辑 BUG / 代码实现 BUG数组越界忘记continue。边界和易错点1. 仅需遍历前 n-1 堆最后一堆会自动匹配平均值无需处理2. 当前堆已等于平均值时直接跳过不产生移动操作3. 注意区分本题「一次移任意张算 1 次」与糖果传递「每移 1 张算 1 次」的模型差异4. 本题为线性结构不可套用环形均分的中位数解法。下次看到什么信号我应该想到这个方法看到「线性排列 相邻移动 均分物品 最少操作次数每次移任意张计 1 次」直接对应线性均分纸牌模型优先用从左到右的贪心递推求解。AC 完整代码#includeiostream#includealgorithm#includevectorusingnamespacestd;intmain(){intn;cinn;vectorintv(n);intsum0;for(inti0;in;i){cinv[i];sumv[i];}intavesum/n;intans0;for(inti0;in-1;i){if(v[i]ave){continue;}else{ans;v[i1](v[i]-ave);v[i]ave;}}coutans;return0;}