本题的基本策略是:将所有的颜色按照数量从高到低排列。我们优先对当前数量最多(a)的颜色取一个球,这样总价值+a。然后再对当前剩余数量最多(b)的颜色取一个球(可能仍然是同一种颜色),这样总价值+b...直到我们操作的次数达到orders。
举个例子,我们将inventory从高到低排序之后,假设数组长这个样子:
10 7 4 3 2 1
第一回合:数值最大的10就是我们的操作目标,我们取一个球,总价值加10分。但是取完之后发现最大数量的颜色依然是它,但是9个球,意味着我们还可以再取一个球再增加9分。我们可以不断地取这个颜色,直至该颜色的数目和第二多的颜色数目持平(都是7)。所以这一轮我们的价值增加的是(10+9+8).
第二回合:当前数值最大的7就是我们的操作目标。注意这次我们可以取2个球:包括颜色数量排名第一和第二的两种颜色。此外,我们可以从+7,+6,一直取到+5(因为数量第三多的颜色数量是4),故增加的价值是(7+6+5)*2
可见每个回合,我们就推进了一种颜色。在处理第i种颜色时,我们可以一轮取i+1个球,这些球对应的分值是相同的,从inventory[i]、inventory[i]+1...直至inventory[i+1]+1。
这里有一个比较关键的地方,就是总球数达到orders的时候,我们必须停下来。在哪个回合的哪一轮停下来,“零头”是多少,需要好好处理。从上述可知,在第i回合中,每轮可以取i+1个球,可知需要进行q = orders/(i+1)
轮,剩下的零头r = orders%(i+1)
个球对应的分数就是inventory[i]-q
.
另一个注意的点是,对于10 10 8....
这种情况,根据上述的算法,第一回合其实不用做任何操作,因为第一和第二的颜色数目相同。在第二回合的操作里直接一并取两个球。
因为每轮我们所取的球的分值都是递减1的,我们可以尝试猜测最后一整轮的球的分值是k,另外可能还有一些零头的球它们的分值是k-1. 我们需要寻找最大的k,使得分值大于等于k的球的总数不超过orders。
对于任何一种颜色inventory[i],如果inventory[i]>=k,那么它必然能贡献inventory[i]-k+1个球,其中最大分数是inventory[i],最小分数是k。扫描一遍整个数组,我们就能把总球数求出来,与orders比较一下。如果大于orders,说明取的球太多了,k要提升一下。反之,k就要下降一点。
确定了k之后,我们还要手工计算一下零头的数量是多少,他们每个球贡献的分数是k-1.