平均

问题描述

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

输入格式

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

输出格式

输出一行包含一个正整数表示答案

Code

n = int(input())

#每个数ai都是区间[0，9]的整数，所以创建列表，里面存放0-10中每个数字是第几个数
numbers = [[] for i in range(10)]

#长度为n的数组输入
for i in range(n):
    a, b = map(int,input().split())
    numbers[a].append(b)                #例如数字1，是第1,2,3个

ans = 0                         #代价为0
k = n//10                       #长度为n，有n//10个10
for i in range(10):
#对numbers[i]中的数进行从小到大排序，因为不用替换的数为最大的数
#例如：1，是第1，2，3，不用替换的数为3，即最大的数3
    ls = sorted(numbers[i])     
#代价和为-k前面的数的和;因为有k个代价最大的数，为保证代价尽可能小，这些k个代价就不用，就加到倒数第k个之前的代价
    ans += sum(ls[:-k])
print(ans)