Readme

2233.Maximum-Product-After-K-Increments

这道题的贪心策略非常明显。因为所有元素的和是固定的（包括原来的sum加上新增的K）、元素数目是固定的，那么尽量让这些元素变得相等，是让乘积最大化的唯一策略。

因为本题对于元素的操作是只增不减，所以我们需要将K都分配给较小的元素，尽量“共同富裕”。那么我们将nums排序之后，需要将K分配给前多少个较小元素呢？显然我们要找到一个位置p，使得前p个元素之和加上K之后再进行平均分配，依然达不到第p+1个元素. 为什么呢？如果前p个元素进行共产主义之后，均值大于了第p+1个元素，那为什么不在前p+1个元素内进行“共同富裕”呢，这样就有更多的元素可以趋近一致，从而使乘积更大化。

那么我们如何快速定位这个p呢？我们定义diff数组diff[i] = presum[i]+K - nums[i]*(i+1)，表明将前i+1个元素都提升至与nums[i]相等的话，需要多少“支援”。可以知道，这个diff一定是递增的。于是我们可以用二分找到最大的p，使得恰好diff[p]<=K，意味着K的支援能够将nums[0:p]抹平，但是不足以将nums[0:p+1]抹平。

我们接下来的任务就是，用presum[p]+K这些数量在前p+1个元素内平均分配。注意可能会有余数。我们令each = (presum[p]+K)/(p+1)表示每个元素至少能分配到each；再令extra = (presum[p]+K)%(p+1)表示有这么多余数，可以让extra元素能分配到each+1. 所以最终结果就是把extra个each+1，p+1-extra个each，以及从p+1开始的剩余的nums相乘。