#数组变换

来源：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 的元素必须是非负整数

#解答

-- 随机生成输入
local N = math.random(3, 10)
local A = {}
local B = {}

for i = 1, N do
    A[i] = math.random(0, 99)
    B[i] = 0
end

-- 打印数组
local function print_array(prefix, arr, suffix)
    io.write(prefix .. "[")
    for i = 1, #arr do
        io.write(arr[i])
        if i < #arr then io.write(", ") end
    end
    io.write("]")
    if suffix then
        io.write(suffix)
    end
end

print(string.format("\nN:%d", N))
print_array("A:", A, '\n')

-- 计算 sum(A)
local function sum(arr)
    local s = 0
    for i = 1, #arr do s = s + arr[i] end
    return s
end

local SA = sum(A)

-- 检查 k 是否整数
local k = SA / (N - 1)
if SA % (N - 1) ~= 0 then
    print(string.format("1.无法转换（k=%f 不是整数），请重试。", k))
    return
end

k = math.floor(k)

-- 计算 excludes
local excludes = {}
for i = 1, N do
    excludes[i] = k - A[i]
end

-- 检查 excludes 是否有负数
for i = 1, N do
    if excludes[i] < 0 then
        io.write("2.无法转换（")
        print_array("excludes=", excludes)
        print(" 包含负数），请重试。")
        return
    end
end

-- 打印步骤
print("具体步骤:")
print_array("B:", B)
print(" <- 开始")

for i = 1, N do
    local v = excludes[i]
    for _ = 1, v do
        -- B = [x+1 for x in B]
        for j = 1, N do
            B[j] = B[j] + 1
        end
        -- B[i] -= 1（注意 Lua 下标从 1 开始）
        B[i] = B[i] - 1

        print_array("B:", B)
        print(string.format(" <- 排除 %d", i - 1))  -- Python 的下标从 0 开始
    end
end

-- 打印结果
print(string.format("总共需要 %d 次。", k))
print_array("excludes: ", excludes)
>>> Establishing WebAssembly Runtime. 
>>> Standby. 
Powered by Shift.