信息学奥赛一本通T1432-糖果传递(数学递推的应用)

解题思路:https://blog.csdn.net/qq_41890797/article/details/90244567            公式推理

**代码解释：**

**输入处理：**

* 读取小朋友的数量 `n`。

* 对于每个小朋友，读取其原有的糖果数量 `a[i]`。

**计算总糖果数和平均糖果数：**

* 计算所有小朋友的糖果总数 `sum`。

* 计算平均糖果数 `ave` 为 `sum / n`。

**递推计算 `b[i]`：**

* `b[i]` 表示从第 `i` 个小朋友传给第 `i+1` 个小朋友的糖果数量。

* 对于每个小朋友 `i`，计算 `b[i]` 为 `(ave - a[i]) + b[i-1]`。

**排序和计算中位数：**

* 对 `b` 数组进行排序。

* 中位数是排序后数组中间的元素。`b[(n+1)/2]` 是中位数。

**计算最小代价：**

* 对于每个小朋友 `i`，计算 `abs(mid - b[i])`，表示使第 `i` 个小朋友获得平均糖果数所需的糖果数量。

* 将所有小朋友的糖果数量求和得到最小代价 `ans`。

**输出最小代价：**

* 输出 `ans`。

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

int a[1000005];//a[i]表示第i个小朋友原有的糖果数量

long long b[1000005];//b[i]表示从第i个小朋友传给第i+1个小朋友的数量

long long sum=0;

int n;

long long ans=0;

int main(){

    cin>>n;

    for(int i=1;i<=n;i++){

        cin>>a[i];

        sum+=a[i];

    }

    long long ave=sum/n;//平均数

    for(int i=1;i<=n;i++){//递推b[i]

        b[i]=(ave-a[i])+b[i-1];

    }

    sort(b+1,b+n+1);

    long long mid=b[(n+1)/2];//求中位数

    for(int i=1;i<=n;i++){

        ans+=abs(mid-b[i]);

    }

    cout<<ans<<endl;

    return 0;

}