我们考虑某一个数的A[i]和它对应的index i。
我们先考虑A[i]<=i
,此时根据规则我们知道A[i]对应的得分已经是1。 我们可以知道,每做一次左移,A[i]对应的index就会减1。所以当左移i-A[i]+1
次之后,此时的元素位置变成A[i]-1,根据规则得分变为0. 如果将原始数组左移i+1
次,那么元素会跑到数组的最后位置(即N-1),根据规则,得分又变成了1。举个例子,如果A="XXXX2XX",那么左移0次到n-1次,分别对应的得分就是1110011。
我们设立一个差分数组diff,其中diff[k]表示在左移k次之后A[i]对应的得分变化。于是我们就有
diff[0] += 1;
diff[i-A[i]+1] -= 1;
diff[i+1] += 1;
对于A[i]>i
,根据规则,初始状态是得0分。当左移i+1次之后,元素跑到了数组的最后一个,一定小于index(即N-1),故得分开始变成1. 当再左移N-A[i]次后,元素跑到了A[i]的位置,此时得分开始变成0.举个例子,如果A="XX4XXXX",那么左移0次到n-1次,分别对应的得分就是0001110。我们不难总结出:
diff[0] += 0;
diff[i+1] += 1;
diff[i+1+N-A[i]] -= 1;
有了上面两种情况,我们可以处理每个A[i],计算它所贡献的diff[k],其中k=0,1,2...,N-1表示左移的次数。
最后在diff数组里找到最大的diff[k],其中k就对应着rotate多少次能使所有A[i]的得分总和最大。
另外,两种情况也可以统一写成
diff[(i-A[i]+1+N)%N] -= 1;
diff[i+1] += 1;