[BZOJ1045][HAOI2008]糖果传递(数学分析)

题目:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1045

分析:均分纸牌的环状版本。

先看线性的版本:

设f[i]表示第I位从第i+1位得到的糖果数

则f[i]=tot/n-a[i]+f[i-1]

对f[]求和就行了

对于环状版本也这么考虑,唯一特殊的就是a[1]可以给a[n],不妨设给了k个

那么f[n]=f[n]-k,那么往前推f[n-1]=f[n-1]-k,……,于是每个f[i]=f[i]-k

所以最后结果为singma(f[i]-k),求他的最小值很明显就是在数轴上一些点,求一个点使得距离和最短,果断去中位数那个点……

原文地址:https://www.cnblogs.com/wmrv587/p/3900279.html