博客

线形均分纸牌：

有N堆纸牌，每堆的纸牌数为a[i]，牌只能在左右相邻传递，若传递一张纸牌的代价为1，问最小代价是多少？

首先毫无疑问最后每堆牌里都有ave张牌

假设p[i]表示第i堆给第i+1堆的牌数

我们的目标是 |p[1]|+|p[2]|+…+|p[n]| 最小 (线形的话p[n]=0)

有p[i]=a[i]+p[i-1]-ave

p[i]-p[i-1]=a[i]-ave

p[i-1]-p[i-2]=a[i-1]-ave

…

p[2]-p[1]=a[2]-ave

上述式子相加得到p[i]-p[1]=sigma(a[2]~a[i])-(i-1)*ave

记b[i]=sigma(a[j]-ave) j=2,3,4…,i

那么p[i]-p[1]=b[i]

对于线型来说 p[n]=0 b[n]可以求得 所以p[1]是确定的 从而p[2] p[3]也能确定

环形均分纸牌：

环形p[n]!=0所以p[1]是不能确定的

我们可以把环从某个位置断开变成一条链，可以分成n条链

暴力可以把n种情况都求得取最小值

但其实可以贪心的去做 p[1]取b[]的中位数（只要是中间数的区间内都行）就行了（参考货仓选址）

目标函数变为 Min( |b[1]-(-p[1])| + |b[2]-(-p[1])| + … + |b[n]-(-p[1])| )

-p[1]即为中位数

代码：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
using namespace std;
const int maxn = 1e6+7;
const int inf = 1e9+7;
typedef long long LL;
int n;
LL a[maxn],sum,ave,b[maxn],ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        sum+=a[i];
    }
    ave=sum/n;
    for(int i=2;i<=n;i++)
        b[i]=b[i-1]+a[i]-ave;
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++)
        ans+=abs(b[i]-b[(n+1)/2]);
    printf("%lld\n",ans);
	return 0;
}