在经过了一系列问题的铺垫之后，终于来到boss这关了。。
糖果传递问题（和仓库运输问题一样的，这里给出糖果传递的题目）：
老师准备了一堆糖果，恰好n个小朋友可以分到数目一样多的糖果．老师要n个小朋友去拿糖果，然后围着圆桌坐好，第1个小朋友的左边是第n个小朋友其他第i个小朋友左边是第i-1个小朋友。大家坐好后，老师发现，有些小朋友抢了很多的糖果，有的小朋友只得到了一点点糖果，甚至一颗也没有，设第ai个小朋友有ai颗糖果．小朋友们可以选择将一些糖果给他左边的或者右边的小朋友，通过”糖果传递”最后使得每个小朋友得到的糖果数是一样多的，假设一颗糖果从一个小朋友传给另一个小朋友的代价是1，问怎样传递使得所耗的总代最小。
一、由均分纸牌引发的思考；
这题和均分纸牌的不同之在于是形成了环。如果没有环，我们显然可以使用贪心算法算出其最小的代价，时间复杂度为O(n)；将环拆开形成一列，这样就可以在求得一个“最优”，拆开的方式有n种。选出最优的，即是解了。
why？因为在一列中的贪心算法是这样问题定义的，将向下一个相邻的节点索取这样，而且从第一个到最后一个是可以完成我们对问题的求解。所以这里将问题转换为均分纸牌问题，时间复杂度为O(n*n)；
参考均分纸牌代码，稍微修改可得一下代码，未经过优化工作，利于理解：
1 int func35(int arr[], int n) 2 { 3 assert(arr && n>0); 4 5 int i,cnt,sta; 6 long avg=0; 7 int *a; 8 int less=INT_MAX; 9 10 if (n<2) 11 { 12 return 0; 13 } 14 a = new int[n]; 15 for (i=0; i<n; i++) 16 { 17 //a[i] = arr[i]; 18 avg += arr[i]; 19 } 20 avg /= n; 21 22 for (sta=0; sta<n; sta++) //起始位 23 { 24 for (i=0; i<n; i++) //相当于移位 25 { 26 a[i] = arr[(sta+i)%n]; 27 } 28 29 cnt = 0; 30 for (i=0; i<n-1; i++) 31 { 32 33 cnt += abs(a[i] - avg); 34 a[i+1] = a[i+1] + a[i] - avg; 35 } 36 if (less > cnt) 37 { 38 less = cnt; 39 } 40 } 41 42 delete[] a; 43 44 return cnt; 45 }
可是，时间复杂度过高，要是ACM绝对是超时的。
更细的看问题，先将问题看成一列，即将1和n之间拆开环，求解跟均分纸牌是一样的：
A： 1 2 4 5 1 2 4 5
B： -2 -1 1 2 -2 -1 1 2
C： -2 -3 -2 0 -2 -3 -2 0
A为原数组，原有的糖果数；B为减去AVG平均数的值；C为前i项B的和，即c[i]=b1+...+bi；
则以a[1]开头（1与n之间拆开）的最优为∑abs(c[i])，这个没问题；
现在考虑从a[2]开头：
A： 1 2 4 5 1 2 4 5
B： -2 -1 1 2 -2 -1 1 2
C1： 0 -1 0 2 0 -1 0 2
显然，B数组没有改变，而C1变了。其中C1可以这么算全部减去b[1]（考虑C是如何算的）
将其一般化：假设起点为k，那么以此起点开始操作的费用为：∑abs(c[i]-c[k-1]) （相当于求和的从第I到第J的和=（从1到j的和）-（从1到i的和）），是不是感觉漏了点什么呢？不是有环么？旋转了么？环形的思想已经在其中了，怎么解释？有木有发现C（C1中最后一个元素是c[1]）最后的一个元素一定是0，这个是一个关键点。这样你从k开始，那么c[k-1]-c[k-1]=0前一个就成为了新的最后一个；自行证明，这里实在太巧了。。。
如果从a[3]开头：C2： 1 0 1 3 1 0 1 3 (c2[i] = c[i]-c[3])
这样就是说通过计算：∑abs(c[i]-c[k-1])这个就可以计算出以某处断裂的最优，在其全部的最优，即是所求了；
观察发现：即是找c中的某个数c[k]使得∑abs(c[i]-c[k-1])最小，中位数可以使其达到最优解，这个就不证明了。华丽转身，问题转换成求中位数了。
1 int func36(int a[], int n) 2 { 3 assert(a && n>0); 4 5 int i,cnt; 6 long avg=0; 7 int *c; 8 9 if (n<2) 10 { 11 return 0; 12 } 13 14 for (i=0; i<n; i++) 15 { 16 avg += a[i]; 17 } 18 avg /= n; 19 20 c = new int[n]; 21 22 for (i=0 ; i<n; i++) //求b数组 23 { 24 c[i] = a[i] - avg; 25 } 26 27 for (i=1 ; i<n; i++) //求c数组 28 { 29 c[i] = c[i-1] + c[i]; 30 } 31 32 sort(c, c+n); //排序以便求中位数 33 34 cnt = 0; // 35 36 for (i=0; i<n; i++) 37 { 38 cnt += abs(c[i]-c[n/2]); 39 } 40 41 delete[] c; 42 43 return cnt; 44 }
当然在求中位数的时候，还可以稍微提速。
二、由石子合并引发的思考；
A： 1 2 4 5 1 2 4 5
B： -2 -1 1 2 -2 -1 1 2
问题的转换：应该转换为对B数组的相邻元素的合并，为什么呢？试想：对糖果数的移动，无非就是对每堆糖果数的差值进行调和，最后的和为0；思想就是这样的，至于细节，就在于如何计分上了，这里出现的负数。
然后就没有然后了，没有想出如何解决。。。
只是提一个思路，不知道是否可行；
既然可以使用贪心算法，估计也可以使用动态规划实现的。。。
P.S. 重点不是文章中写得如何得好或详细，而是学会将这些问题关联起来，打通任督二脉 \(^o^)/~
原文链接：http://www.cnblogs.com/legendmaner/archive/2013/05/07/3062222.html