【数学】【HAOI2008】【BZOJ1045糖果传递】【BZOJ3293分金币】论数学的重要性

BZOJ1045和BZOJ3293一模一样两道题，在这里我用1045来讲。

1045: [HAOI2008] 糖果传递

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 3518 Solved: 1633
[Submit][Status][Discuss]

Description

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

Input

　　第一行一个正整数n<=987654321，表示小朋友的个数．接下来n行，每行一个整数ai，表示第i个小朋友得到的
糖果的颗数．

Output

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

Sample Input

4
1
2
5
4

Sample Output

Solution

　　刚看这道题的时候满脑子图论，甚至搜索都想出来了，最后看蓝书上对这道题数学方法的讲解才恍然大悟。

　　数学太麻烦了自己看小蓝书吧【手动滑稽】

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 int N,mid;

 int A[],C[];

 long long ans,M;

 long long my_abs(int x){if(x<) x=-x; return x;}

 int main(){

     scanf("%d",&N);

     for(int i=;i<=N;++i) scanf("%d",&A[i]),M+=A[i]; M/=N;

     for(int i=;i<=N;++i) C[i]=C[i-]+(A[i]-M);

     sort(C+,C+N+); mid=C[N>>|];

     for(int i=;i<=N;++i) ans+=my_abs(mid-C[i]);

     printf("%lld",ans);

     return ;

 }