Python 数组数字均衡化 最小代价算法

给定一个长度为 n 的数组（n 是 10 的倍数），每个数 ai 都是区间 [0, 9] 中的整数。小明发现数组里每种数出现的次数不太平均，而更改第 i 个数的代价为 bi，他想更改若干个数的值使得这 10 种数出现的次数相等（都等于 n/10 ），请问代价和最少为多少。

首先统计每种数出现的次数，然后计算出每种数需要更改的次数。 对于每个需要更改的位置，选择更改最小代价的数，直到每种数出现的次数都相等为止。

代码如下：

n = int(input())
a = list(map(int, input().split()))
b = [[0] * 10 for _ in range(10)]  # b[i][j] 表示将数字 i 更改为 j 的代价
for i in range(10):
    b[i] = list(map(int, input().split()))
cnt = [0] * 10
for x in a:
    cnt[x] += 1
avg = n // 10
cost = 0
for i in range(10):
    if cnt[i] < avg:
        for j in range(avg - cnt[i]):
            min_cost = float('inf')
            min_idx = -1
            for k in range(n):
                if a[k] == i:
                    continue
                c = b[a[k]][i]
                if c < min_cost:
                    min_cost = c
                    min_idx = k
            a[min_idx] = i
            cnt[i] += 1
            cost += min_cost
print(cost)