如何构造行列和均为k且元素极差最小的N阶整数矩阵

构造元素均为整数的N×N矩阵，满足两项约束：

• 矩阵每一行、每一列的元素和均等于给定值k
• 矩阵内元素的最大值与最小值的差值最小

原有实现代码在部分输入下无法满足行列和要求，例如输入6 11时输出矩阵行列和不达标、元素分布不合理；输入5 6时正确结果应为主对角线元素为2、其余元素为1的矩阵。

原有错误代码如下：

n , k = map(int,input().split())
matrix = [[k//n]*n for i in range(n)]

def row_sum(matrix,row):
    return sum(matrix[row])

def col_sum(matrix,col):
    res = 0
    for i in matrix:
        res += i[col]
    return res


for i in range(n):
    for j in range(n):
        if (row_sum(matrix,i) != k) and (col_sum(matrix, j) != k):
            matrix[i][j] += 1

for i in matrix:
    print(*i)

• 初始值设置逻辑是正确的：先将所有元素赋值为k//n，此时每行每列的和为n*(k//n)，距离目标和k还差r = k % n的总值，只需要给每行、每列总共r个位置加1即可凑够目标和。
• 加1的判断逻辑完全错误：使用「行和不达标且列和不达标」作为加1条件，既无法保证每行恰好加r次1，也无法保证每列恰好加r次1，最终必然出现行列和不满足要求的问题。
• 每次判断都重新遍历计算整行、整列的和，存在不必要的性能损耗。

要让矩阵元素最大值和最小值的差值最小，理论上的最小差值只能是0或1：

• 当r = k % n == 0时，所有元素都等于k//n，差值为0，直接输出全a矩阵即可。
• 当r>0时，矩阵元素只能取a = k//n和a+1两个值，差值为1，不可能存在差值更小的合法矩阵（如果所有元素都等于a，行和仅为n*a <k，无法满足和为k的要求）。

此时问题转化为：在矩阵中选出r*n个位置，保证每行恰好有r个选中位置、每列恰好有r个选中位置，将选中位置的值设为a+1，其余位置设为a，即可同时满足行列和要求、差值最小要求。
最简单的构造方式是循环移位选点：对第i行，依次选择列号为(i + t) % n（t取值从0到r-1）的位置加1，即可自动满足每列恰好有r个选中位置的要求。

n, k = map(int, input().split())
base = k // n
remainder = k % n
matrix = [[base] * n for _ in range(n)]

for row_idx in range(n):
    for offset in range(remainder):
        col_idx = (row_idx + offset) % n
        matrix[row_idx][col_idx] += 1

for row in matrix:
    print(*row)

效果验证 #

• 输入5 6时，base=1，remainder=1，每行仅选主对角线位置加1，输出正好是主对角线为2、其余为1的正确结果，行列和均为6，元素差值为1。
• 输入6 11时，base=1，remainder=5，每行有5个位置为2、1个位置为1，每列也恰好有5个位置为2、1个位置为1，行列和均为5*2 + 1*1 =11，元素差值为1，完全符合要求。

内容的提问来源于stack exchange，提问作者Hadi