CH122 糖果传递题解报告

淩亂°似流年 2021-11-02 09:42 196阅读 0赞

[题目传送门][Link 1]

**【题目大意】**

有$n$个小朋友坐成一圈，第$i$个小朋友有$a\_i$个糖果，每个小朋友可以向左右两个小朋友传递糖果，每人每次传递糖果要耗费1单位体力，求最少耗费多少体力可以使每个小朋友最后拥有的糖果数相等。

**【思路分析】**

首先算出最后每个小朋友拥有的平均糖果数$s$，设$X\_i$表示第$i$个小朋友给第$i-1$个小朋友的糖果数，$X\_1$表示第1个小朋友给第$n$个小朋友的糖果数，若$X\_i<0$表示第$i-1$个小朋友给第$i$个小朋友糖果。所以我们可以得出如下的结论：

$$a\_1-X\_1+X\_2=s\\Rightarrow X\_2=s-a\_1+X\_1=X\_1-c\_1(c\_1=a\_1-s)$$

$$a\_1-X\_2+X\_3=s\\Rightarrow X\_3=2s-a\_1-a\_2+X\_1=X\_1-c\_2(c\_2=2s-a\_1-a\_2)$$

$$……$$

$$a\_n-X\_n+X\_1=s\\Rightarrow X\_1=X\_1-c\_\{n-1\}(c\_\{n-1\}=(n-1)\*s-a\_1-…-a\_\{n-1\})$$

因为$ans=|X\_1|+…+|X\_n|$，所以我们要保证$|X\_i|$之和最小，即

$$|X\_1|+|X\_1-c\_1|+…+|X\_1-c\_\{n-1\}|(min)$$

整理过后整个式子中只剩下$X\_1$一个变量，这个式子的集合意义就是在数轴上找到一个点$X\_1$，使得这个点到$0,c\_1,…,c\_\{n-1\}$这$n$个点的距离总和最小，而符合条件的这个点就是这些数值的中位数。

**【代码实现】**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<iostream>
     3 #include<cstring>
     4 #include<algorithm>
     5 #include<cmath>
     6 #define g() getchar()
     7 #define rg register
     8 #define go(i,a,b) for(rg int i=a;i<=b;i++)
     9 #define back(i,a,b) for(rg int i=a;i>=b;i--)
    10 #define db double
    11 #define ll long long
    12 #define il inline
    13 #define pf printf
    14 using namespace std;
    15 int fr(){
    16     int w=0,q=1;
    17     char ch=g();
    18     while(ch<'0'||ch>'9'){
    19         if(ch=='-') q=-1;
    20         ch=g();
    21     }
    22     while(ch>='0'&&ch<='9') w=(w<<1)+(w<<3)+ch-'0',ch=g();
    23     return w*q;
    24 }
    25 const int N=1000002;
    26 int n,a[N],c[N];
    27 ll sum,ans;
    28 int main(){
    29     n=fr();
    30     go(i,1,n) a[i]=fr(),sum+=a[i];
    31     int s=sum/n;
    32     go(i,2,n) c[i]=c[i-1]+a[i]-s;
    33     sort(c+1,c+1+n);
    34     int mid=c[n/2+1];
    35     go(i,1,n) ans+=abs(c[i]-mid);
    36     pf("%lld\n",ans);
    37     return 0;
    38 }

代码戳这里

转载于:https://www.cnblogs.com/THWZF/p/11272994.html

[Link 1]: https://www.acwing.com/problem/content/124/
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/dfa5a80ef73541b29a26ce4bb195fb67.png