#数组变换

来源：stackoverflow

#题目

给定一个长度为 N 的任意整数数组 A 和另一个长度相同的全零数组 B。可以多次进行如下操作：

每次将数组 B 中的 N-1 个元素的值加一

判断能否通过多次操作，将数组 B 变换为数组 A，给出需要进行的操作次数。

#分析

数组 B 的长度为 N，每次将数组 B 中的 N-1 个元素的值 +1；也就意味每次 有且仅有一个 元素的值不 +1。

假设：

通过 k 次操作可以将数组 B 变换为数组 A
数组 excludes 的元素 excludes[i] 表示 B[i] 没被 +1 的次数

则有：

sum(excludes) 等于 k
A[i] 等于 k - excludes[i]

因此：

sum(k - A[i]) == k
N*k - sum(A) == k
(N-1)*k == sum(A)
k == sum(A) / (N-1)

注意：

k 必须是非负整数
excludes 的元素必须是非负整数

#解答

import random

# 随机生成输入
N = random.randint(3, 10)
A = [random.randint(0, 99) for _ in range(N)]
B = [0 for _ in range(N)]

print(f'\nN:{N}\nA:{A}')

# 检查 k 是否是整数
k = sum(A) / (N-1)
if sum(A) % (N-1) != 0:
    print(f'1.无法转换（k={k} 不是整数），请重试。')
    quit()

# 计算 k 和 excludes
k = sum(A) // (N-1)
excludes = [k - v for v in A]

# 检查 excludes 是否包含负数
if (any(v < 0 for v in excludes)):
    print(f'2.无法转换（excludes={excludes} 包含负数），请重试。')
    quit()

# 打印步骤
print('具体步骤:')
print(f'B:{B} <- 开始')
for i,v in enumerate(excludes):
    for _ in range(v):
        B = [v + 1 for v in B]
        B[i] = B[i] - 1
        print(f'B:{B} <- 排除 {i}')

# 打印结果
print(f'总共需要 {k} 次。')
print(f'excludes: {excludes}')
>>> Establishing WebAssembly Runtime. 
>>> Standby. 
Powered by Shift.