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

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

题目描述

有n nn个小朋友坐成一圈，每人有a i a_iai​个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1 11。

输入格式

小朋友个数n nn，下面n nn行a i a_iai​。

输出格式

求使所有人获得均等糖果的最小代价。

输入输出样例 1

输入 1

4 1 2 5 4

输出 1

4

说明/提示

对于100 % 100\%100%的数据1 ≤ n ≤ 10 6 1 \leq n\le 10^61≤n≤106，1 ≤ 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_{i=1}^{n}{a_i}∑i=1n​ai​是n nn的倍数。

思路分析

这是一个经典的环形均分纸牌问题。设总糖果数为sum，平均值为avg = sum / n。定义c[i] = a[i] - avg，表示第i个人与平均值的差值。设x[i]表示第i个人给第i+1个人的糖果数（可为负，负表示反向传递），则最终每个小朋友的糖果数变为a[i] - x[i] + x[i-1]（下标模n）。令其等于avg，得到：

x[i] = x[i-1] + c[i]

定义前缀和s[0] = 0，s[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的数据。

代码实现

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e6+5;intn;ll a[N],s[N];// a:原糖果数, s:前缀和(差值累积)intmain(){// 加速输入输出ios::sync_with_stdio(false);cin.tie(0);cin>>n;ll sum=0;for(inti=1;i<=n;++i){cin>>a[i];sum+=a[i];}ll avg=sum/n;// 平均值// 计算前缀和s[i] = sum_{j=1}^{i} (a[j] - avg)// s[0] = 0 隐含，数组从1开始存s[1..n-1]，最后需要0..n-1共n个值s[0]=0;for(inti=1;i<n;++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,s+n);// 取中位数ll med=s[n/2];// 计算最小代价ll ans=0;for(inti=0;i<n;++i){ans+=abs(s[i]-med);}cout<<ans<<"\n";return0;}

功能分析

1. 输入处理：使用ios::sync_with_stdio(false)和cin.tie(0)加速，读取小朋友个数n及每个人的糖果数a[i]，同时计算总糖果数sum。
2. 平均值计算：avg = sum / n，因为题目保证总和是n的倍数，故avg为整数。
3. 构造前缀和数组：s[0] = 0，s[i] = s[i-1] + (a[i] - avg)（i=1..n-1）。得到n个值s[0] ~ s[n-1]。
4. 排序取中位数：对s数组排序，中位数为s[n/2]（下标从0开始）。
5. 计算最小代价：遍历所有s[i]，累加|s[i] - med|，结果即为最小传递代价。
6. 输出：打印答案。

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;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++标准模板库STL：
https://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 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}