date: 2020-02-02 21:19:38

题目

输入输出格式

分析思路

n个小朋友围成一个环，然后每个人只能给左右两个人传递糖果
且传递x个糖果消耗的代价为x

第一直觉肯定是糖果多的人怎么传给糖果少的人
一时半会看不出来用什么方法可以解决问题，我们于是可以先建立一个数学模型

建立数学模型

我们可以设n个小朋友现在手里的糖果数分别为A1,A2,A3 … ,An-1,An
我们约定，从An传递到An-1为Xn个糖果数

其中,Xn为正表示糖果从An传递到An-1

反之如果为负，则表示从An-1传递到An

则依题意可知我们最终要求的就是|X1| + |X2| + |X3| + … + |Xn|的最小值

第二次做题的思路

然后转化成求一个点到各个C[i]的距离之和最小，就是排序之后的C[i]数组的中点到各个C[i]点之差的和即为最小的距离之和

代码如下

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;
const int N = 1000000 +10;
typedef long long LL;
int A[N],C[N],S[N];//A[i]记录原数据,S[i]为A[i]的前缀和数组
LL n,sum = 0,avg,res;

int main()
{
    scanf("%lld",&n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%d",&A[i]);
        sum += A[i];
        S[i] = S[i-1]+A[i];
    }
    avg = sum / n;
    for(int i = 1;i <= n;i++)
    {
        C[i] = S[i-1]-avg*(i-1);
    }
    sort(C+1,C+1+n);
    for(int i = 1;i <= n;i++)
    {
        res += abs(C[n/2]-C[i]);
    }
    cout<<res;

    return 0;
}

第一次做题的思路

那么，显而易见最后每个点的结果一定是Ā
每个点起初都是Ai，结果都是Ā
那么我们通过每个点可以得到n个关系式
即
A1 - X1 + X2 = Ā
A2 - X2 + X3 = Ā
A3 - X3 + X4 = Ā

…

An-1 - Xn-1 + Xn = Ā
A1 - Xn + X1 = Ā

整理上式
X1 - X2 = A1 - Ā
X2 - X3 = A2 - Ā
…
Xn-2 - Xn-1 = An-2 - Ā
Xn-1 - Xn = An-1 - Ā
Xn - X1 = An - Ā

感觉跟差分数列差不多的样子
于是我们从最后一项依次递加i项
比如最后两项相加可以得到X2 = X1 - ((n-1)Ā - An - An-1 -…- A2)
最后三项相加可以得到X3和X1的关系
依次类推
我们可以得到Xi与X1的一个线性关系
从而我们可以把所有的Xi转换成X1+Ci继续进行求解

继续整理
Xn = X1 - (Ā - An)
Xn-1 = X1 - (2Ā - An - An-1)
…
X2 = X1 - ((n-1)Ā - An - An-1 -…- A2)
X1 = X1

于是我们要求的|X1| + |X2| + |X3| + … + |Xn|
可以转换成|X1 - C1| + |X1 - C2| + |X1 - C3| + … + |X1 - Cn|

即转换成在直线上求一点X使得X到C1,C2,C3,…,Cn的距离最小

其中
C1 = Ā - An
C2 = 2Ā - An - An-1
…
Cn-1 = (n-1)Ā - An - An-1 -…- A2
Cn = 0

可以发现其中的一个递推关系就是
Cn - Cn-1 = Ā - An-1
又C1 = Ā - An
我们可以根据这个递推关系求出所有的Ci
然后再对Ci从小到大排序
找到Ci的中间的点就是使得它到其他Ci距离之和最小的点

注意点

1.数列最好从1开始方便计算
2.当数列从1开始的时候，中间点即为(n+1)/2，需要+1
3.数据可能爆int，所以要用long long 长整形表示结果

总结

这题是AcWing 104. 货仓选址的一个进阶题目，或者说是区间选点加了一个套子
难点在于我们在考试的时候如果遇到这种题很难静下心来去分析出题目的数学模型并进行进一步的整理
所以需要我们多做题多总结模型才行啊（

代码如下：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;
const int N = 1000000 +10;
typedef long long LL;
int A[N],C[N],S[N];//A[i]记录原数据
LL n,sum = 0,avg;

int main()
{
    cin>>n;
    for(int i = 1;i <= n;i++)
    {
        scanf("%d",&A[i]);//数据范围较大最好用scanf进行输入
        sum += A[i];//计算所有糖果的和
    }
    avg  = sum / n;//计算糖果的平均值
    int k = 1;
    C[k] = avg - A[n];//初始化，C[1] = Ā - An
    for(int i = n;i > 1;i--)
    {
        C[k+1] = C[k] + avg - A[i-1];//根据Cn - Cn-1 = Ā - An-1递推关系来算出所有C[i]的值
        k++;
    }
    C[n] = 0;
    sort(C+1,C+n+1);//对各个点到原点的距离进行排序
    LL res = 0;
    for(int i = 1;i <= n;i++)
    {
        res += abs(C[(n+1)/2] - C[i]);//找到中间的那个点再计算到其他个点的距离之和
    }
    cout<<res;//因为数据保证一定有解，所以我们直接输出res
    return 0;
}

AcWing 122. 糖果传递-贪心