[CQOI2011] 分金币

· · 题解

题目传送门

没做此题的不要看

题意

有 n 个干草堆组成一个环，在第 i 个位置有 a[i] 个干草堆，可以将任意位置的干草堆向前或向后移动若干个，使第 i 个位置有 ans 个干草堆，询问最少需要移动多少个干草堆。

思路

实则就是均分纸牌的升级版，其贪心思想也是本题要用到的。

即可规定一个方向，这里我规定向左，每堆牌都向左传，变成 ans 个，若本不足 b[i] 个咋办呢，那就向左索要，其实等价于传负数个，详细看这位大佬的 blog。

注：以上链接博客均非本人所有

那么我们可设每个位置原有 a[i] 个，要变成 ans 个，向左传递（左右都可以，单一方向即可，这里规定向左）x[i] 个。

则所求值为 \sum _ {i = 1}^n\min(| x[i] |)。

由题意我们可知：

ans=a[1]+x[2]-x[1] ans=a[2]+x[3]-x[2]

依次推得当 1 \le i < n 时：

ans=a[i]+x[i+1]-x[i] ans=a[n]+x[1]-x[n]

可得：

x[2]=ans+x[1]-a[1] x[3]=ans+x[2]-a[2]=ans+(ans+x[1]-a[1])-a[2] ans+(ans+x[1]-a[1])-a[2]=2 \times ans-a[1]-a[2]+x[1]

即：

x[3]=2 \times ans-a[1]-a[2]+x[1]

对于 2 \le i \le n 有：

x[i]=\sum_{j=1}^{i-1}(ans-a[j]) + x[1] x[1]=\sum_{j=1}^{n}(ans-a[j]) + x[1]

不妨设：

c[1]=a[1]-ans c[2]=a[1]+a[2]-2 \times ans

对于 1 \le i \le n 则有：

c[i]=\sum_{j=1}^{i}(a[j]-ans)

即可知道：

x[2]=x[1]-c[1] x[3]=x[1]-c[2]

当 2 \le i \le n 时：

x[i]=x[1]-c[i-1] x[1]=x[1]-c[n]

所以：

\sum _ {i = 1}^n\min(| x[i] |)

等价于：

\sum _ {i = 1}^n\min(| x[1]-c[i] |)

放在数轴上来讲就是点 x[1] 到 c[i] 的距离和的最小值，此处 1 \le i \le n。

那么 x[1]=c[\frac{n+1}{2}] 时就一定可取最小值，这个就不说明了，自己思考一下为什么。

对于 1 \le i \le n，c[i] 我们是已知的。那么，本题完。

等等，还有代码！

代码

#include<bits/stdc++.h>
using namespace std;
long long n,a[1000001],c[1000001],sum,mid,ans;
int main(){
    //经验: p2512 UVA11300 p3051 p4016 p2125 p5817 SP11117
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];
    sum/=n;
    for(int i=1;i<=n;i++)c[i]=c[i-1]+a[i]-sum;
    sort(c+1,c+1+n);mid=c[(n+1)/2];
    for(int i=1;i<=n;i++)ans+=abs(mid-c[i]);
    cout<<ans;
}