线性代数 + 中位数

完全用的是教材里面的算法

时间复杂度

通过排序求中位值, 因此, 时间复杂度是O(n*log(n))
如果通过”快速选择”算法求中位值, 时间复杂度是O(n)

Python 代码

def solution():
    def cal(A):
        n = len(A)
        avg = sum(A) // n
        for i in range(n):
            A[i] -= avg
        for i in range(1, n):
            A[i] += A[i - 1]
        A.sort()
        median = A[n // 2]
        return sum(abs(e - median) for e in A)

    N, M, T = map(int, input().split())
    rows = [0] * N
    cols = [0] * M

    for i in range(T):
        x, y = map(int, input().split())
        rows[x - 1] += 1
        cols[y - 1] += 1
    mrows = T % N
    mcols = T % M
    if mrows and mcols:
        print("impossible")
        return
    if not mrows and not mcols:
        print(f"both {cal(rows) + cal(cols)}")
    elif not mrows:
        print(f"row {cal(rows)}")
    else:
        print(f"column {cal(cols)}")


solution()