题意
n个小孩坐一圈,第i个小孩刚开始有A[i]个糖块。
小孩只能把糖块给身边的两个人(第1个小孩可以把糖块给第n个小孩)
每人每次传递一个糖块代价是1。
求把糖块平均分配的总代价最少是多少。
分析
单向传递
若要使传递次数最小,一个人只能跟上一个人进行一次传递(可正可负)。即构成一个单向(顺时针/逆时针)环。 边的值代表送出的糖块数量,可正可负。
存在一个最优解,使这个环的一条边的权值为0 (即可以把这个环切断成一个链进行求解
反证法:
如果不存在一个无环最优解,则只存在有环最优解。设其中正值边数为k
,总边数为n
。并且正值边数量小于等于负值边数量(若大于,逆转环的方向即可)。第i条边的权值为li
。总成本L = ∑|li|
对所有边+a, 仍是此问题的一个解(但不一定最优),下面探究a的值对总成本的影响
取负数里面|li|
最小为lx
, 正数里面|li|
最小为ly
。
在lx
, ly
之间取a,并且加到每个边上。
新的总成本为 L1 = L + k * a - (n-k) * a
即 L1 = L + (2k - n) * a
由于正值边少于等于负值边,有2k - n <= 0
, 可以取a为lx。
此时新的方案总成本不致增加,仍是最优解,甚至更优。并且存在一条边为0。
若已知k,使最优解的链从k开始
从别的题解 易知 解法如下:
记 C[i] = A[i] - avg;
Sk[i] = Sk[i-1] + C[i]
//S[i]是从k开始的前缀和
ans = ∑|Sk[i]|
不知道k,如何求解?
Sk[i] = S[i] - S[k-1]
(k <= i <= n)
Sk[i] = S[n] - S[k-1] + S[i] = S[i] - S[k-1]
(0 < i < k) (S[n] = 0)
这样以来,∑|Sk[i]|
便化成了 ∑|S[i]-S[k-1]|
的最小值
所以应该选择S[]
中的中位数作为S[k-1]
(可参考AcWing104货舱地址中的优秀题解) (若中位数有两个,随便选择一个)
AC代码如下
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll a[1000005];
ll c[1000005];
ll s[1000005];
ll n;
ll lug(ll arr[], ll l, ll r){
ll k = rand() % (r-l);
ll temp = arr[k+l];
arr[k+l] = arr[l];
arr[l] = temp;
ll pvoit = arr[l];
ll lo = l;
ll hi = r-1;
while(lo < hi){
while(lo < hi && arr[hi] > pvoit) hi--;
if(lo < hi) arr[lo++] = arr[hi];
while(lo < hi && arr[lo] < pvoit) lo++;
if(lo < hi) arr[hi--] = arr[lo];
}
arr[lo] = pvoit;
return lo;
}
ll getKth(ll arr[], ll l, ll r, ll k){
ll x;
while(k != (x = lug(arr, l, r))){
if(x < k)
l = x+1;
else
r = x;
}
return arr[k];
}
int main(void){
scanf("%lld", &n);
ll sum = 0;
for(ll i = 1; i <= n; i++){
scanf("%lld", a+i);
sum += a[i];
}
ll avg = sum / n;
for(ll i = 1; i <= n; i++){
c[i] = a[i]-avg;
s[i] = s[i-1]+c[i];
}
ll mid = getKth(s, 1, n+1, (n+1)>>1);
long long ans = 0;
for(ll i = 1; i <= n; i++){
ans += abs(s[i]-mid);
}
printf("%lld", ans);
}