思路:多年以前写蓝书碰见过,似乎与求中位数有关,只记得当时只是稀里糊涂地抄了思路,但是现在却完全忘记了,还是说明重在理解而不是抄抄抄。
X
i
X_i
Xi代表第
i
i
i个人给上一个人的糖果数,
X
i
<
0
X_i<0
Xi<0就是拿走上一个人糖果的数目。
a
v
e
为
a
i
的平均数
ave为a_i的平均数
ave为ai的平均数 于是有:
a
i
+
X
(
i
+
1
+
m
o
d
)
%
m
o
d
−
X
i
=
a
v
e
a_i+X_{(i+1+mod)\%mod}-X_i=ave
ai+X(i+1+mod)%mod−Xi=ave 有
n
n
n个未知数,分别是
X
1
,
X
2
,
X
3
.
.
.
X
n
X_1,X_2,X_3...X_n
X1,X2,X3...Xn 然而把前
n
−
1
n-1
n−1个式子相加得到:
∑
i
=
1
n
−
1
a
i
+
X
n
−
X
1
=
(
n
−
1
)
∗
a
v
e
\sum_{i=1}^{n-1}a_i+X_n-X_1=(n-1)*ave
∑i=1n−1ai+Xn−X1=(n−1)∗ave 与最后一项比较:
a
n
+
X
1
−
X
n
=
a
v
e
a_n+X_1-X_n=ave
an+X1−Xn=ave 显然,前
n
−
1
n-1
n−1项的求和左侧添加
a
n
+
X
1
−
X
n
a_n+X_1-X_n
an+X1−Xn可以得到右侧,说明最后一项等式是与前
n
−
1
n-1
n−1是等价的,
n
−
1
n-1
n−1个方程,
n
n
n个式子,我们没有办法解方程得到答案,但我们仍能把它们用一个变量表示起来. 用
X
1
X_1
X1表示上述若干个式子.
X
2
=
a
v
e
−
a
1
+
X
1
X_2=ave-a_1+X_1
X2=ave−a1+X1
X
3
=
a
v
e
−
a
2
+
X
2
=
a
v
e
−
a
2
+
a
v
e
−
a
1
+
X
1
=
2
∗
a
v
e
−
(
a
1
+
a
2
)
+
X
1
X_3=ave-a_2+X_2=ave-a2+ave-a1+X_1=2*ave-(a1+a2)+X_1
X3=ave−a2+X2=ave−a2+ave−a1+X1=2∗ave−(a1+a2)+X1
X
4
=
3
∗
a
v
e
−
(
a
1
+
a
2
+
a
3
)
+
X
1
X_4=3*ave-(a1+a2+a3)+X_1
X4=3∗ave−(a1+a2+a3)+X1
X
i
=
(
i
−
1
)
∗
a
v
e
−
∑
j
=
1
i
−
1
a
j
+
X
1
X_i=(i-1)*ave-\sum^{i-1}_{j=1}a_j+X_1
Xi=(i−1)∗ave−∑j=1i−1aj+X1 花费就是:
∑
i
=
1
n
∣
X
i
∣
\sum_{i=1}^{n}|X_i|
∑i=1n∣Xi∣ 仔细观察,除了
X
1
X_1
X1外,前面的
(
i
−
1
)
∗
a
v
e
−
∑
j
=
1
i
−
1
a
j
(i-1)*ave-\sum^{i-1}_{j=1}a_j
(i−1)∗ave−∑j=1i−1aj是一个定值 不妨设为
−
C
i
-C_i
−Ci,
C
i
=
∑
j
=
1
i
−
1
a
j
−
(
i
−
1
)
∗
a
v
e
C_i=\sum^{i-1}_{j=1}a_j-(i-1)*ave
Ci=∑j=1i−1aj−(i−1)∗ave 为什么要把绝对值里面的式子变成一个减法的形式,是为了套接下来的一个模型：仓库选址 变形完,变为求
∑
i
=
1
n
∣
C
i
−
X
1
∣
\sum_{i=1}^{n}|C_i-X_1|
∑i=1n∣Ci−X1∣ 等价以下问题:给定
n
n
n个数轴上的点,选取其中的一个点,使得其他点到它的距离之和最短。 直观想象,这个点就是中点.故只用求出该中点即可 这个问题为什么是中点,鄙人学力有限,各位可以查看相关证明资料。
/*
Stairs upon the temple
I climb and I crawl in
People travel millions of miles just to see it
But they never conquer this way
*/#includeusingnamespace std;constint maxn =1e6+5;constint INF =1e9+7;typedeflonglong ll;typedef pair<int,int> pii;#defineall(a)(a).begin(),(a).end()#definepb(a)push_back(a)
vector<int> G[maxn];
ll C[maxn];ll a[maxn];intmain(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);int n;cin>>n;
ll ave =0;for(int i=1;i<=n;i++) cin>>a[i],ave+=a[i];
ave/=n;for(int i=2;i<=n;i++){
C[i]= C[i-1]+ a[i-1]- ave;}sort(C+1,C+1+n);
ll x = C[(n+1)/2];
ll ans =0;for(int i=1;i<=n;i++){
ans+=abs(C[i]-x);}
cout<<ans;}
