AcWing 122. 糖果传递(y总视频解法)
原题链接
中等
作者:
何锦仙
,
2024-03-17 22:37:51
,
所有人可见
,
阅读 6
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e6+10;
ll a[N];
ll sum=0;
ll c[N];//x1所需到的点;
int main(){ // 双向问题贪心一般只考虑单向,破环为链;
ll n;
scanf("%d", &n);
for(int i=1;i<=n;i++){
cin >> a[i];
sum+=a[i];
}
ll ave=sum/n;//a(平均);
// a[2]给a[1]的个数为x2,a[i]给a[i-1]的个数为xi,a[1]给[n]的个数为x1;
//有a1给an x1个,收到a2的x2个,结果达到平衡(平均数);
//a[1]-x1+x2=a(平均);............................1
//a[2]-x2+x3=a(平均);............................2
//...
//a[n-2]-x(n-2)+x(n-1)=a(平均);
//a[n-1]-x(n-1)+xn=a(平均);......................n-1
//a[n]-xn+x1=a(平均);............................n
//题目要求的其实就是|x1|+|x2|+...+|xn|;
//所以写出x(i)的表达式;
// xn-x1 =a[n]-a; == x1-(a-a[n]) .... x1-c[n]
//第n项加上(n-1)项,得x(n-1)-x1=(a[n]+a[n-1])-2*a; == x1-(2*a-(a[n]+a[n-1])); .... x1-c[n-1]
//倒数三项相加得 x(n-2)-x1=(a[n]+a[n-1]+a[n-2])-3*a;
//递推 x(i)-x1=(a[n]+a[n-1]+..+a[i])-(1-i)*a;
// x1 = x1-0; .... x1-c[1]
//也就是定一个点x1,使得x1这个点到各个点的距离之和最小;
for(int i=n;i>1;i--){
c[i]+=ave+c[i+1]-a[i]; //录入各个点;
}
c[1]=0;
sort(c+1,c+1+n);
ll ans=0;
for (int i =1,j=n;i<j;i++,j--)ans+=c[j]-c[i];
//for (int i = 1; i <= n; i ++ ) ans += abs(c[i] - c[(n + 1) / 2]);
printf("%lld\n", ans);
return 0;
}
为什么 如果没有sum,直接用ave来完成求平均数会报错;