AcWing_122 糖果传递(推公式、贪心)

AcWing

122. 糖果传递

假设小朋友的编号从$1$到$n$，$x_i$表示小朋友$i$传递给小朋友$i+1$的糖果数量，特殊地，$x_n$表示小朋友$n$传递给小朋友$1$的糖果数量。数组$a[N]$表示小朋友原先有的糖果数量，$aver$表示每个小朋友糖果数量的平均值。那么有：

$ans = min{\lvert x_1 \rvert + \lvert x_2 \rvert + \cdots + \lvert x_n \rvert}$

$aver = a_1 - x_1 + x_n$，即$x_1 = x_n - (aver - a_1)$

$aver = a_2 - x_2 + x_1 = x_n + (a_1 + a_2 - 2aver)$，即$x_2 = x_n - (2aver - a_1 - a_2)$

$\cdots$

$x_{n-1} = x_n - ((n-1)aver - a_1 - a_2 - \cdots - a_{n-1})$

$x_n = x_n - 0$

那么$ans = min{\lvert x_1 \rvert + \lvert x_2 \rvert + \cdots + \lvert x_n \rvert} = min{\lvert x_n - s_1 \rvert + \lvert x_n - s_2 \rvert + \cdots + \lvert x_n - s_n \rvert}$.

即，在数轴上寻找一个点，使得其到点{$s_1$, $s_2$, $\cdots$, $s_n$}的距离之和最小，只需要找到这些点在数轴上的中位数，即为$x_n$，再求距离之和。

#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 1000010;
int a[N];
typedef long long LL;
LL s[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    
    LL sum = 0;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        sum += a[i];
    }
    int aver = sum / n;
    
    LL res = 0, tmp = 0;    // a[i]向a[i + 1]传递的糖果
    for(int i = 1; i <= n; i ++) s[i] = s[i - 1] + aver - a[i];
    sort(s + 1, s + n + 1);
    
    int mid = (n + 1) / 2;
    LL v = s[mid];
    for(int i = 1; i <= n; i ++) res += abs(v - s[i]);
    
    cout << res;
    return 0;
}