1148 G. Balanced Distribution
题意:
给定长度为\(n\)的环序列\(a_0,\cdots,a_{n-1}\)和常数\(k\),保证序列平均值是整数.每次操作将环上连续\(k\)个数在和不变的前提下重新分配值.求最少操作次数使得所有值一样,并输出方案.
题解:
- 考虑线段上的情况.如果最左边的\(k\)个数和大于\((k-1)\bar a\),可以将前\((k-1)\)个数分配为\(\bar a\),将剩余的值分配给第\(k\)个数,然后递归地处理右边剩下的\((n-k)\)个数.否则,先处理右边\((n-k)\)个数,并且要使得第\(k\)个数足够大能够完成前\(k\)个数的分配.此时,同样先考虑这部分最左边的\(k\)个数的和是否能完成分配.
实现中可以使用递归函数distribute(l,len,need)表示处理以\(l\)为起点,\(len\)为长度的区间,并且最左侧需要额外的\(need\)值.外部以distribute(0,n,0)的方式调用.具体细节参考代码.
可以发现,每次长度会减少\(k-1\),并且当长度恰为\(k\)的时候只需要处理一次,因此需要操作\(\lceil\dfrac{n-1}{k-1}\rceil\).
- 如果区间\([x,y]\)满足\(\displaystyle\sum_{i=x}^ya_i=(y-x+1)\bar a\),那么就能单独处理这一段区间.这个条件也可以写成\(\text{prefix_sum}_y-y\bar a=\text{prefix_sum}_{x-1}-(x-1)\bar a\).因此可以将所有满足\(\text{prefix_sum}_i-i\bar a\)相等的位置作为断点(将\(i\)和\(i+1\)断开).
- 假设有两段相邻的区间长度分别为\(x\)和\(y\),分开操作需要\(\lceil\dfrac{x-1}{k-1}\rceil+\lceil\dfrac{y-1}{k-1}\rceil\),合并操作需要\(\lceil\dfrac{x+y-1}{k-1}\rceil\),注意,当且仅当\(x\equiv y\equiv1\pmod{k-1}\)的时候,合并操作次数会更少.因此,应该将环分解成若干模\(k-1\)余1的区间,否则直接对整个环当成线段进行操作.
- 长度模\(k-1\)余1等价于两个断点位置模\(k-1\)的意义下相差\(1\),因此在每种\(\text{prefix_sum}_i-i\bar a\)相等的位置中找到某些断点使得它们位置模\(k-1\)是一个连续的递增(每次在模的意义下\(+1\))序列.由于是环,考虑倍长位置序列(倍长后半部分需要\(+n\)).从后往前扫得到每个断点最近的下一个合法位置(即该位置模\(k-1\)意义下是当前位置\(+1\)),然后用倍增的方法得到合法的下\(2^i\)个位置.然后从倍长前半部分的每个位置出发,判断是否能够在若干步后走到倍长的后半部分的对应位置(即从\(i\)经过若干步到\(i+n\)).从这些合法的位置选一个步数最长的作为答案.最后,根据这些断点对每个区间进行第一步所述的分配.
代码
1148 G. Balanced Distribution
原文：https://www.cnblogs.com/Heltion/p/12329221.html
