如果是链的话就是均分纸牌，如果再改一下条件就有点像长城守卫...感觉模型都很类似的感觉....
先来看看均分纸牌怎么做，咱们先求平均数，求出每一份纸牌的需求量，然后从左往右取，为什么可以贪心？因为左边的链的纸牌一定是从它相邻右边那个来的，而它多余的纸牌也一定是给右边的，所以直接取就可以了。那么这个就不行了。这个是环形的，咱们假设咱们拆成链的话，那么还有一种可能就是最左边给了最右边一些纸牌，这样贪心不成立。但是咱们也可以做，咱们可以假设一口气给了右边K张之后就不再给（假设分多次给的话不如一次给），这样就强行拆成链状了。那么关键是求多少个K为好。
对于均分纸牌，设i堆给右边p[i]张纸牌，设每一堆纸牌为a[i]，则总的操作数为∑p[i],然后咱们又有递推式
a[i]+p[i-1]-ave=p[i].则∑abs(p[i]) 就是答案。
这里展开下不难发现 p[i]=∑a[j] - j*ave
然后就是 环状，环可以拆成链，但是它不满足贪心的性质，可是咱们可以让他满足，咱们之前假设了从头到末一次性给了K张，且之后不再给了，那么它就变成了均分纸牌了（假设分别给两次显然还不如直接给）
那么 咱们的 a[1]=a[1]-k,则 p[1]=p[1]-k,则p[2]=p[2]-k,p[3]=p[3]-k......而a[n]=a[n]+k,p[n-1]=p[n-1]-k。即所有的p[]都变小了。
即 ∑abs（p[i]-k)最小，显然这货就是p的中位数最好。
=================================
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define maxn 1000010
using namespace std;
int n,a[maxn],p[maxn];
long long sum=0;
int main()
{
int i;
scanf("%d",&n);
memset(p,0,sizeof(p));
for (i=0;i<n;i++) scanf("%d",&a[i]),sum+=a[i];
sum=sum/n;
for (i=0;i<n;i++) a[i]-=sum,p[i]=i==0?a[i]:p[i-1]+a[i];
sort(p,p+n);
for (i=0,sum=0;i<n;i++) sum+=abs(p[i]-p[n>>1]);
printf("%lld",sum);
system("pause");
return 0;
}
评论