平均

问题描述

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

输入描述

输入的第一行包含一个正整数 n。

接下来 n 行，第 i 行包含两个整数 ,ai,bi，用一个空格分隔。

思路

方法比较笨，利用字典来记录ai元素所对应的所有bi，再利用题目给出的每个元素出现次数为n/10这个值 ，将每个ai中bi元素超过的， 从小到大累加起来

参考代码

n = int(input())
dic = {}
for i in range(n):
    a,b = map(int,input().split())
    if a not in dic:
        dic.update({a:[b]})
    else:
        lis = dic.get(a)
        lis.append(b)
mi = n // 10
result = 0
for i in dic:
    dic.get(i).sort()
    if len(dic.get(i)) > mi:
        size = len(dic.get(i)) - mi
        result += sum(dic.get(i)[0:size])

print(result)

输入

10
1 1
1 2
1 3
2 4
2 5
2 6
3 7
3 8
3 9
4 10

输出

27