糖果传递

题目描述

有 $n$ 个小朋友坐成一圈，每人有 $a_i$ 个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为 $1$。

思路

我们可以找到均分后第 $i$ 个是缺牌，还是多牌，那么完成均分的代价就是多牌向缺牌的路径，因此怎样选择会是更优答案呢？

如果我用前缀和 $sum[i]$来表示这 $i$ 个人的手牌

举个例子 $i_3 = {1,0,-1}$, 显然 $sum[i_3] = 0$ 有什么用呢？

如果我在 $-1$ 右边加一个 $k$ ，那么

$sum[i_4] - sum[i_0] = k $ ,定义为 $a$

$sum[i_4] - sum[i_1] = k - 1$，定义为 $b$

$sum[i_4] - sum[i_2] = k - 1$,定义为 $c$

则有 $abs(a + c +b)$ 刚好为是价值，$k$ 在左边同理

那么总价值就可以表示成：

\[\sum_{i=1}^{N}|Sum[i]-Sum[k]| \]

要想价值最小，找 $k$ 是关键！

这里引入一个 “货仓选址” 问题，即你需要找出所有货仓到达你选择的距离之和最短，很显然，选择中位数是最优解，前缀和就可以搞定

我们可以发现，这刚好和我们总价值的思路很想呀，对不对！

那么最优解就是可以找到了~~

看代码

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
#define int long long
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();

    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;

        ch = getchar();
    }

    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }

    return x * f;
}

const int manx = 1e7;
int n,a[manx],sum[manx],ave,ans;
 main(){
     n = read();
     for(int i = 1;i <= n; i++){
         a[i] = read();
         ave += a[i]; 
     }
     ave /= n;//平均值
     for(int i = 1;i <= n; i++) a[i] -= ave;
     for(int i = 1;i <= n; i++){
         sum[i] = sum[i - 1] + a[i];
     }
     sort(sum+1,sum+1+n);// 先排序
     int t = sum[(n+1)>>1];// 最好的K （中位数）
     for(int i = 1;i <= n; i++) ans += abs(t - sum[i]);
     cout<<ans;
 }

糖果传递

糖果传递

推荐阅读