题解 | 元素方碑：“能量守恒”，但只能在奇或偶数位置转移

import sys

test_num = int(input())

for i in range(test_num):
    cur_len = int(input())
    cur_list = list(map(int,input().split()))
    # 1、排除无法整除的list
    if sum(cur_list)/len(cur_list) != int(sum(cur_list)/len(cur_list)):
        print('NO')
    else:
		# 目标值，列表总和÷列表长度
        target = int(sum(cur_list)/len(cur_list))
		# 计算和目标list的差距
        gap_list = [target - x for x in cur_list]
        # print(gap_list)
		# 计算所有偶数位、奇数位之和，都为0时，即可满足要求
		# 可以理解为，所有奇数位都是"连通"的，只要和为0，一定可以调整成目标值
		'''
		比如：
		cur_list=[3,1,2,1,3], 则要调整为的目标值target=10/5=2
		gap_list=[-1,1,0,1,-1]
		观察发现，偶数位一定可以通过若干次调整，变成相同的数值，和具体在第2个还是第4个位置无关；奇数位同理
		'''
        sum_ou,sum_ji=0,0
        for j in range(0,cur_len,2):
            sum_ou += gap_list[j]
        for j in range(1,cur_len,2):
            sum_ji += gap_list[j]
        # print(f'sum_ou={sum_ou},sum_ji={sum_ji}')
        if sum_ou==0 and sum_ji ==0:
            print('YES')
        else:
            print('NO')
    

一定要拿本子写呀，找两个示例就能发现规律！

比如：

cur_list=[3,1,2,1,3], 则target=10/5=2

gap_list=[-1,1,0,1,-1]

我们的目标是让gap_list中的值全部为0！

观察发现，想要调整为0，对于下面的红色1：

gap_list=[-1,1,0,1,-1]

需要调整其两边奇数位置的-1和0，就有2种情况：

1、他们如果和为0，那就好办，若干次相同方向的转移即可；

2、如果不为0，那就要考虑下一位可以转移的位置，一定也是在奇数位置，即最后的蓝色加粗-1：gap_list=[-1,1,0,1,-1]。同样的道理，如果他们和为0，也可以通过若干次转移达到和target的值差距为0.....

不难发现，所有的奇数位都是“联通的”！，因此，只需关注所有奇数位与目标值target之间的差距gap之和是不是为0，是的话就可以；不是，如上面的例子，可以理解为“能量守恒”，但只能在相隔位（也就是奇数位或偶数位）之间传递。当然偶数位也要满足。