我们任意挑出一对数nums[i]和nums[n-1-i],将其中较小的数记做a,较大的数记做b。
如果我们不做任何操作,它们的和一定就是a+b。
如果我们允许操作一次将其中一个数变大,那么它们的和的范围可以是[a+b+1,limit+b].如果我们还想将和变得更大,只能操作两次,使得和的范围达到[limit+b+1,2*limit].
如果我们允许操作一次将其中一个数变小,那么它们的和的范围可以是[a+1,a+b].如果我们还想将和变得更小,只能操作两次,使得和的范围达到[2,a+b-1].
所以我们在整个[2,2*limit]的区间上,可以画出“操作次数/pair-sum”的函数曲线:
-----
2 a+1 a+b a+b+1 limit+b+1 2*limit
____ ________________
|_________ _________|
|_|
也就是说,我们对于nums[i]和nums[n-1-i],想要这对pair sum处于[2,a]时,至少需要两次操作(将两个数都变小);想要pair sum处于[a+1, a+b-1]时,至少需要一次操作(将其中的b变小);想要pair sum等于a+b时,不需要操作;想要pair sum处于[a+b+1,limit+b]时,至少需要一次操作(将其中的a变大);想要pair sum处于[limit+b+1, 2*limit]时,至少需要两次操作(将两个数都变大)。
如果我们将所有的函数曲线叠加,就可以得到一个新的函数曲线:如果令所有的pair sum都相同,那么从这个曲线的纵坐标上就可以读出总共需要多少次操作。
我们接下来需要做的就是扫一遍这个叠加的函数曲线,找到它的最小值。
我们如何叠加这么多的单个曲线呢?首先,对于单个曲线而言,我们不需要描述出每个位置的操作次数。因为每条单个曲线都是五段的分段函数,我们只需要记录下每处拐点和差分值即可。当x=0的时候,y=0;当x=2的时候,diff[x]=2,也就是说经过这个位置之后相应的操作次数变动为 y+=2. 当x=a+1的时候,diff[x]=-1,也就是说经过这个位置之后需要的操作次数变成 y-=1. 同理,我们会设置diff[a+b]=-1, diff[a+b+1]=+1, diff[limit+b+1]=+1, diff[2*limit]=+1. 其他的位置diff[x]都等于0.
最终计算每处x对应的y值(需要的最少操作数)时,只需要更新y+=diff[x]即可。