AcWing 122. 糖果传递 环形纸牌均分问题分析
原题链接
中等
作者:
一塌糊涂
,
2023-01-08 22:43:40
,
所有人可见
,
阅读 250
//环形纸牌均分问题:
/*
n个人构成一个环:
假设 Xn:表示 a_n+1 给 a_n 的糖果数量 可正可负:
所以我们要求的 ans = min |X1| + |X2| + ... + |Xn|
因为题目一定有解:我们假设 最后的平均数是 avg(a)
也就是我们最终的状态是:每个 a_i 都变成呢 avg(a)
a_1 + X1 - Xn = avg(a)
a_2 + X2 - X1 = avg(a)
a_3 + X3 - X2 = avg(a)
...
...
a_n-1 + Xn-1 - Xn = avg(a)
a_n + Xn - X1 = avg(a)
因为我们的 ans 是X_i 表示的:
我们得想方法表达出X_i,而且形式得具有一般规律性
X1 = Xn - a_1 + avg(a)
X2 = X1 - a_2 + avg(a)
X3 = X2 - a_3 + avg(a)
(这边其实就是猜测:你把X1代入代入X2,再把X2代入X3,会凑出一般规律)
X1 = Xn - a_1 + avg(a)
X2 = Xn - a_1 - a_2 + 2*avg(a)
X3 = Xn - a_1 - a_2 - a_3 + 3*avg(a)
...
...
Xn-1 = Xn - a_1 - a_2 - a_3 -...-a_n-1 + (n-1)*avg(a)
Xn = Xn
你会发现Xn后面的形式:类似前缀和
我们设 C[i] = a_1 + a_2 + ... + a_i - i*avg(a)
补充定义:C[0] = 0
C[i]实际就是个前缀和数组:我们可以处理出来 !
给每个Xi加上绝对值相加:就是我们要求的形式,但要得到min
绝对值看成距离 min(|Xn - C[0]| + |Xn - C[1]| + |Xn - C[2]| + ... + | Xn - C[n-1]|)
|Xn-C[i]|的几何意义: 是数轴上的点Xn到C[i]的距离
这就变成了经典的:邮递员投递问题 【AcWing 104. 货仓选址】
*/
cpp
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define fastio cin.tie(0)->sync_with_stdio(false);cout.tie(0)
#define N 1000005
int a[N];
long long c[N];
int main()
{
fastio;
int n;cin>>n;
long long sum = 0;
for(int i=1;i<=n;i++) {
cin>>a[i];
sum += a[i];
}
long long avg = sum/n;
for(int i=1;i<=n-1;i++){
c[i] = c[i-1] + a[i] - avg;
}
sort(c,c+n);
long long mid = c[n>>1];
long long ans = 0;
for(int i=0;i<=n-1;i++){
ans += abs(c[i] - mid);
}
cout<<ans<<endl;
return 0;
}
写的太好了!