第二题：
多多鸡有一串长度为L的珍珠项链，上面有N颗珍珠，分布在0到L-1这些位置上。现在多多鸡想把所有的珍珠移动到一起，并且想让所有珍珠移动的距离总和尽可能小。所有的珍珠可以看作在一个环上，珍珠可以向相邻没有珍珠的位置移动。请给出最优的方案下，所有珍珠移动的距离的总和。
笔试的时候没有做出来。这个是后来想的，不一定对。
# L = 10
# N = 5
# data = [1,3,5,7,9]
L = 1000
N = 4
data = [1,4,998,995]
data.sort()
flag = [1 if i in data else 0 for i in range(L)]
print(flag)
L= L-1
min_distance = L * N
for i in range(L): # i作为新珍珠项链的中心，其他珍珠都向i移动，放在i的左侧或者右侧
distance = 0
distance1 = 0
distance2 = 0
for num in data: # num表示旧项链上的每个珍珠的位置
if flag[i] == 0: #因为i是空位，所以有两种情况，一种是移动到i左侧的珍珠占用位置i，一种是移动到右侧的珍珠占用位置i。
# （1）左侧占用位置i
if num > i:
d_left1 = (L - num) + 1 + i - sum(flag[num+1:]) - sum(flag[:i])
# 如果num放在i的左侧，并且num大于i，那么移动的距离等于num先移动到旧项链尾部的距离，加上穿越尾部到旧项链头部后从头部移动
# 到i处的距离，减去num和i之间的在num右侧和i左侧的其他珍珠的个数。因为左侧占用位置i，所以计算距离时要包括i
d_right1 = (num - (i+1)) - sum(flag[i + 1:num])
# 如果num放在i的右侧，并且num大于i，那么移动的距离等于num直接向左移动到i的距离，加上num左侧和i的右侧之间其他珍珠的个数。
else:
d_left1 = (i - num) - sum(flag[num+1:i])
# 如果num放在i的左侧，并且num小于i，那么移动的距离等于num直接向右移动到i的距离，加上num右侧和i的左侧之间的其他珍珠的个数。
d_right1 = num + 1 + (L - (i+1)) - sum(flag[:num]) - sum(flag[i+1:])
# 如果num放在i的右侧，并且num小于i，那么移动的距离等于num先向左移动到旧项链头部的距离，再加上穿越到头部到旧项链尾部后从尾
# 部向左移动到i的距离，减去在i右侧和num的左侧的其他珍珠的个数
print("i=",i,'num=',num,'d_right1=',d_right1, 'd_left1=',d_left1, 'distance=(',distance1, distance2, ')')
# (2) 右侧占用位置i
if num > i:
d_left2 = (L - num) + i - sum(flag[num+1:]) - sum(flag[:i])
# 如果num放在i的左侧，并且num大于i，那么移动的距离等于num先移动到旧项链尾部的距离，加上穿越尾部到旧项链头部后从头部移动
# 到i处的距离，减去num和i之间的在num右侧和i左侧的其他珍珠的个数。因为右侧占用位置i，所以计算距离时不能包括i
d_right2 = (num - i) - sum(flag[i+1 : num])
# 如果num放在i的右侧，并且num大于i，那么移动的距离等于num直接向左移动到i的距离，加上num左侧和i的右侧之间其他珍珠的个数。
else:
d_left2 = ((i-1) - num) - sum(flag[num+1:i])
# 如果num放在i的左侧，并且num小于i，那么移动的距离等于num直接向右移动到i的距离，加上num右侧和i的左侧之间的其他珍珠的个数.
# 并且右侧占用位置i，所以计算距离是不能包括i。
d_right2 = num + 1 + (L - i) - sum(flag[:num]) - sum(flag[i:])
# 如果num放在i的右侧，并且num小于i，那么移动的距离等于num先向左移动到旧项链头部的距离，再加上穿越到头部到旧项链尾部后从尾
# 部向左移动到i的距离，减去在i右侧和num的左侧的其他珍珠的个数
distance1 += min(d_left1, d_right1)
distance2 += min(d_left2, d_right2)
print("i=",i,'num=',num,'d_right2=',d_right2, 'd_left2=',d_left2, 'distance=(',distance1, distance2, ')')
else: #如果i不是空位，这个时候就不用分是左还是右，因为都不能占用i。
if num == i:
d_left = 0
d_right = 0
elif num > i:
d_left = (L - num) + (i-1) - sum(flag[num + 1:]) - sum(flag[:i])
# 如果num放在i的左侧，并且num大于i，那么移动的距离等于num先移动到旧项链尾部的距离，加上穿越尾部到旧项链头部后从头部移动
# 到i处的距离，减去num和i之间的在num右侧和i左侧的其他珍珠的个数.
d_right = (num - (i + 1)) - sum(flag[i + 1:num])
# 如果num放在i的右侧，并且num大于i，那么移动的距离等于num直接向左移动到i的距离，加上num左侧和i的右侧之间其他珍珠的个数。
else:
d_left = (i - 1 - num) - sum(flag[num + 1:i])
# 如果num放在i的左侧，并且num小于i，那么移动的距离等于num直接向右移动到i的距离，加上num右侧和i的左侧之间的其他珍珠的个数。
d_right = num + (L - (i + 1)) - sum(flag[:num]) - sum(flag[i + 1:])
# 如果num放在i的右侧，并且num小于i，那么移动的距离等于num先向左移动到旧项链头部的距离，再加上穿越到头部到旧项链尾部后从尾
# 部向左移动到i的距离，减去在i右侧和num的左侧的其他珍珠的个数
distance += min(d_left, d_left)
print("i=",i,'num=',num,'d_right=',d_right, 'd_left=',d_left, 'distance=',distance)
if flag[i] == 1:
if min_distance > distance:
min_distance = distance
else:
if min_distance > min(distance1, distance2):
min_distance = min(distance1, distance2)
print('\n')
print(min_distance)
