uva 11300 Spreading the Wealth

题意:园桌子上坐着n个人,每个人有一定量的金币,每个人可以给左右相邻的人一些金币,最后使得所有的人手中金币数量相同,求送出的金币数量最小

让我想起以前做过的一道贪心题目,在一维坐标轴上,有n个村庄,有的村庄需要买酒,有的村庄需要卖酒,问怎么样分配可以使得运输的酒量最小

最左面的村庄无论是买酒还是卖酒,都要经过他右面的村庄,这样无论右面村庄有没有就,我都从右面买入,这个村庄问题解决以后,那么考虑剩下的村庄的第一个村庄

这道题的不同就是把一维问题变成了环上的问题,每个人的金币来源和去向就有两个方向了,我用c[i]表示我和左面那个人金币的给予量,c[1]表示1给n的量,正数表示i给i-1,负数表示i-1给i,这样我就可以用1维数组把所有人的交易表示出来了,每个人最后手中的金币通过计算为m

那么a1-c1+c2=m

  a2-c2+c3=m

  a3-c3+c4=m

。。。。

然后我用c1表示出所有的c*来,

c2=c1+(-a1+m)=c1-B1

c3=c2-a2=c1+(-a1-a2+2*m)=c1-B2

c4=c3-a3=c1+(-a1-a2-a3+3*m)=c1-B3

c1+|c1-B1|+|c1-B2|+|c1-B3|+...

他的最小值就是我们要的答案

原文地址:https://www.cnblogs.com/jihe/p/5043541.html