平均

问题描述

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

输入格式

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

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

输出格式

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

样例输入

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 个数，需要花费代价 1+2+4+5+7+8=27。

评测用例规模与约定

对于 20% 的评测用例，n≤1000；

对于所有评测用例，n≤10⁵，0<b_i≤2×10⁵。

运行限制

语言	最大运行时间	最大运行内存
C++	3s	512M
C	3s	512M
Java	4s	512M
Python3	5s	512M
PyPy3	5s	512M
Go	5s	512M
JavaScript	5s	512M

来自: 0平均 – 蓝桥云课

我的题解

def ave_nums(lis, n):
    """
    计算列表中数字的平均值。该函数首先根据数字的第二个元素对列表进行降序排序，然后按照数字的首位数进行分组，并计算这些数字的总和。
    
    参数:
    lis: 一个包含数字的列表，每个数字都是一个包含两个元素的列表，第一个元素是数字的首位数，第二个元素是数字本身。
    n: 整数，表示输入的数字列表的长度。
    
    返回值:
    返回所有首位数不重复的数字的总和。
    """
    # 初始化首位数计数字典
    dic = {
        0: 0,
        1: 0,
        2: 0,
        3: 0,
        4: 0,
        5: 0,
        6: 0,
        7: 0,
        8: 0,
        9: 0,
    }
    # 根据数字的第二个元素对列表进行降序排序
    lis.sort(key=lambda x: x[1], reverse=True)
    total = 0  # 初始化总和
    for num in lis:
        # 如果首位数的计数小于n的十分之一，则增加计数
        if dic[num[0]] < (n // 10):
            dic[num[0]] += 1
        else:
            # 否则，将该数字的第二个元素加到总和中
            total += num[1]
    return total


n = int(input())  # 从输入读取数字列表的长度
lis = []  # 初始化数字列表
# 循环读取n个数字，并添加到列表中
for i in range(n):
    a, b = map(int, input().split())
    lis.append([a, b])
# 调用函数并打印结果
print(ave_nums(lis, n))

AI 题解

ERNIE-4.0

这个问题是一个典型的贪心算法问题，我们可以使用贪心策略来解决。

首先，我们需要统计数组中每个数字出现的次数以及更改每个数字的代价。然后，我们可以计算出每个数字需要更改的次数，即当前出现次数与目标次数（n/10）的差值。

接下来，我们可以使用贪心策略来选择要更改的数字。具体地，我们可以维护一个最小堆，其中每个元素是一个二元组，表示一个数字及其更改的代价。然后，我们可以按照代价从小到大的顺序从堆中取出元素，并更新该数字的出现次数，直到该数字的出现次数达到目标次数为止。

最后，我们将所有取出的元素的代价相加，即可得到最小的代价和。

下面是使用 Python 实现的代码：

import heapq

n = int(input())
nums = [0] * 10  # 统计每个数字出现的次数
cost = [[] for _ in range(10)]  # 存储每个数字更改的代价
total_cost = 0  # 最小代价和
target = n // 10  # 目标次数

# 统计每个数字出现的次数以及更改每个数字的代价
for i in range(n):
    a, b = map(int, input().split())
    nums[a] += 1
    heapq.heappush(cost[a], b)

# 贪心选择要更改的数字
for i in range(10):
    diff = nums[i] - target  # 需要更改的次数
    if diff > 0:
        for j in range(diff):
            if not cost[i]:
                break
            total_cost += heapq.heappop(cost[i])

print(total_cost)

需要注意的是，上述代码中使用了 Python 内置的 heapq 模块来实现最小堆。在每次选择代价最小的元素时，我们使用了 heapq.heappop() 函数来弹出堆顶元素，并保证了堆的性质。

另外，由于评测用例规模较大，我们需要注意优化算法的时间复杂度。在上述代码中，我们使用了最小堆来优化选择代价最小的元素的过程，从而将时间复杂度从 O(n^2) 降低到了 O(nlogn)。

---

存档地址：https://www.yuque.com/worthstudy/study/isakl97gcwc9e59r?singleDoc# 《平均》