政务网站设计方案,青海省建设厅网站,网页设计图片紧挨着,推广公司起名1、题目描述
有一个长度为n 的数组#xff08;n 是 10 的倍数#xff09;#xff0c;每个数ai都是区间 [0,9] 中的整数。
小明发现数组里每种数出现的次数不太平均#xff0c;而更改第i 个数的代价为bi#xff0c;
他想更改若干个数的值使得这10 种数出现的次数相等…1、题目描述
有一个长度为n 的数组n 是 10 的倍数每个数ai都是区间 [0,9] 中的整数。
小明发现数组里每种数出现的次数不太平均而更改第i 个数的代价为bi
他想更改若干个数的值使得这10 种数出现的次数相等都等于n/10请问代价和最少为多少。输入格式
输入的第一行包含一个正整数 n
接下来n 行第i 行包含两个整数ai,bi用一个空格分隔。输出格式
输出一行包含一个正整数表示答案。样例输入
10
1 1
1 2
1 3
2 4
2 5
2 6
3 7
3 8
3 9
4 10样例输出
27
样例说明
只更改第 1,2,4,5,7,8 个数需要花费代价 12457827。
2、解析
使得数组中每种数出现次数相等的最小代价 1. 读取n和计算目标出现次数c。 2. 创建一个长度为10的空列表ls用于存储每种数对应的代价。 3. 循环n次读取每个数和对应的代价将代价存储到ls中对应数的列表中。 4. 计算累加代价p遍历ls中的每个列表将其排序并累加除去最大的c个代价值。 3、python代码
nint(input())
cn//10
ls[[] for i in range(10) ]
for i in range(n):a,bmap(int,input().split())ls[a].append(b)
p0
for i in range(10):ls[i].sort()psum(ls[i][:-c])print(p)
4、运行结果
