P2512环形贪心题解复盘

基本信息项目内容题目编号、来源P2512 糖果传递 / 洛谷训练层级B 经典贪心题知识版块贪心算法 / 中位数定理 / 环形均分纸牌 / 前缀和解题前・关键信号识别维度分析目标、约束、底层结构目标环形小朋友均分糖果求最小总传递代价约束只能相邻传递每传递1颗代价1底层结构环形均分问题转化为绝对值距离和最小问题用中位数贪心求解。数据规模n ≤ 1e6数据量大必须使用 long longO(n log n) 可过暴力 O(n²) 超时。候选算法和依据前缀和 中位数贪心依据环形均分纸牌经典模型最小代价等价于所有前缀和到中位数的距离之和最小。复杂度预判O(n log n)排序为瓶颈空间复杂度 O(n)。解题后・外化复盘从会一次到稳定会维度内容实现结构 / 核心思路第一步求出所有人糖果平均值第二步求出每个数与平均值差值的前缀和数组第三步将前缀和数组排序取中位数贪心第四步首尾配对相减累加得到最小代价。前缀和表示前i个人总共多/少了多少个糖果必须通过这条线传递多少个糖果在环形中要找一个地方切开变成线性由数学知识知道这个地方是中位数所以一开始要对前缀和数组排序。然后最大数 - 最小数 次大数 - 次小数 …配对相减这个和就是最小传递次数错因回溯逻辑 BUG / 代码实现 BUG一开始以为和线性一样的解法后面发现环形可以从任意地方切开。边界和易错点1. 数据极大全程必须 long long2. 是差值前缀和不是原数组前缀和3. 环形不能用线性递推必须中位数4. 首尾配对累加等价于中位数总距离和。下次看到什么信号我应该想到这个方法看到「环形 相邻传递 均分物品 最小代价按颗计费」直接锁定环形均分纸牌 / 中位数贪心模板。AC 完整代码#includeiostream#includealgorithmusingnamespacestd;longlongn,p,t,a[1000005],sum[1000005];intmain(){cinn;for(inti0;in;i){cina[i];ta[i];}tt/n;sum[0]a[0]-t;for(inti1;in;i){sum[i]sum[i-1]a[i]-t;}sort(sum,sumn);for(inti0;in/2;i){psum[n-1-i]-sum[i];}coutp;return0;}