网站建设商家宁波seo费用

122. 糖果传递 - AcWing题库

acwing刷题蓝桥杯，糖果传递这道题用到的有数学推导公式，贪心，中位数。解题的关键是找出这个数学推导式

有 n 个小朋友坐成一圈，每人有 a[i] 个糖果。

每人只能给左右两人传递糖果。

每人每次传递一个糖果代价为 1。

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

输入格式

第一行输入一个正整数 nn，表示小朋友的个数。

接下来 nn 行，每行一个整数 a[i]a[i]，表示第 ii 个小朋友初始得到的糖果的颗数。

输出格式

输出一个整数，表示最小代价。

数据范围1≤n≤1000000,
0≤a[i]≤2×10^9,
数据保证一定有解。

 思路：每个小朋友拥有糖果a[1]~a[N]，第一个小朋友给出糖果数X1，第二个给出X2.X3....Xn.。

要求最小的代价，也就是min(|X1|+|X2|+....+|Xn|)，先求出平均糖果数量ave（小朋友最终糖果数量），推导公式转化为求min(|X1-c1|+|X1-c2|+...+|X1-cn|)，

min(|X1-c1|+|X1-c2|+...+|X1-cn|)又可以用 中位数 求。再通过导公式c[i]=c[i+1]-a[i]+ave；将c[1]~c[n]求出即可。不懂中位数的小伙伴可以看文章https://blog.csdn.net/weixin_52797843/article/details/122069259?spm=1001.2014.3001.5501

具体图文详解：

 具体代码实现过程：

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
long long int a[1000100];
long long  c[1000100];
int main()
{int n;cin>>n;long long int sum=0;for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}int ave=sum/n;c[1]=0;for(int i=n;i>1;i--){c[i]=c[i+1]-a[i]+ave;}sort(c+1,c+n+1);long long int count=0;long long int ans=c[(n+1)/2];#中位数for(int i=1;i<=n;i++){count+=abs(c[i]-ans);}cout<<count<<endl;return 0;}

每天的内卷中，不要忘记提升文学素养。

分享一首诗：

绿蚁新醅酒，红泥小火炉。
晚来天欲雪，能饮一杯无？