csp信奥赛C++高频考点专项训练之贪心算法 --【线性扫描贪心】：糖果传递

csp信奥赛C高频考点专项训练之贪心算法 --【线性扫描贪心】糖果传递题目描述有n nn个小朋友坐成一圈每人有a i a_iai​个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1 11。输入格式小朋友个数n nn下面n nn行a i a_iai​。输出格式求使所有人获得均等糖果的最小代价。输入输出样例 1输入 14 1 2 5 4输出 14说明/提示对于100 % 100\%100%的数据1 ≤ n ≤ 10 6 1 \leq n\le 10^61≤n≤1061 ≤ a i ≤ 1.5 × 10 9 1 \leq a _ i \leq 1.5 \times 10 ^ 91≤ai​≤1.5×109∑ i 1 n a i \sum_{i1}^{n}{a_i}∑i1n​ai​是n nn的倍数。思路分析这是一个经典的环形均分纸牌问题。设总糖果数为sum平均值为avg sum / n。定义c[i] a[i] - avg表示第i个人与平均值的差值。设x[i]表示第i个人给第i1个人的糖果数可为负负表示反向传递则最终每个小朋友的糖果数变为a[i] - x[i] x[i-1]下标模n。令其等于avg得到x[i] x[i-1] c[i]定义前缀和s[0] 0s[i] s[i-1] c[i]则x[i] x[0] - s[i-1]。总代价为∑|x[i]| ∑|x[0] - s[i-1]|i从 1 到n。该式在x[0]取s[0], s[1], …, s[n-1]的中位数时最小。因此只需计算前缀和数组s排序后取中位数再累加绝对差即可。时间复杂度O(n log n)空间复杂度O(n)可通过n ≤ 10^6的数据。代码实现#includebits/stdc.husingnamespacestd;typedeflonglongll;constintN1e65;intn;ll a[N],s[N];// a:原糖果数, s:前缀和(差值累积)intmain(){// 加速输入输出ios::sync_with_stdio(false);cin.tie(0);cinn;ll sum0;for(inti1;in;i){cina[i];suma[i];}ll avgsum/n;// 平均值// 计算前缀和s[i] sum_{j1}^{i} (a[j] - avg)// s[0] 0 隐含数组从1开始存s[1..n-1]最后需要0..n-1共n个值s[0]0;for(inti1;in;i){s[i]s[i-1](a[i]-avg);}// 注意s[n-1] sum_{1}^{n-1} (a[i]-avg) - (a[n]-avg)// 因此总共n个值s[0], s[1], ..., s[n-1]// 排序这n个值sort(s,sn);// 取中位数ll meds[n/2];// 计算最小代价ll ans0;for(inti0;in;i){ansabs(s[i]-med);}coutans\n;return0;}功能分析输入处理使用ios::sync_with_stdio(false)和cin.tie(0)加速读取小朋友个数n及每个人的糖果数a[i]同时计算总糖果数sum。平均值计算avg sum / n因为题目保证总和是n的倍数故avg为整数。构造前缀和数组s[0] 0s[i] s[i-1] (a[i] - avg)i1..n-1。得到n个值s[0] ~ s[n-1]。排序取中位数对s数组排序中位数为s[n/2]下标从0开始。计算最小代价遍历所有s[i]累加|s[i] - med|结果即为最小传递代价。输出打印答案。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}