Python堆和优先队列问题案例代码

题目描述

给定m个数字序列，每个序列包含n个非负整数。我们从每一个序列中选取一个数字组成一个新的序列，显然一共可以构造出n^m个新序列。接下来我们对每一个新的序列中的数字进行求和，一共会得到n^m个和，请找出最小的n个和

输入输入的第一行是一个整数T，表示测试用例的数量，接下来是T个测试用例的输入
每个测试用例输入的第一行是两个正整数m（0 < m <= 100）和n(0 < n <= 2000)，然后有m行，每行有n个数，数字之间用空格分开，表示这m个序列
序列中的数字不会大于10000输出对每组测试用例，输出一行用空格隔开的数，表示最小的n个和

样例输入

1
2 3
1 2 3
2 2 3

样例输出

3 3 4

案例代码

首先，我们需要使用堆或优先队列来找到最小的n个和。在Python中，我们可以使用heapq模块来实现堆。

算法如下：

1. 读取测试用例数量T
2. 对于每个测试用例： a. 读取m和n b. 初始化一个空的最小堆 c. 读取m行，每行有n个数，并将它们添加到最小堆中 d. 从最小堆中弹出最小的n个数，并计算它们的和 e. 输出这个和

下面是实现这个算法的Python代码：

import heapq

# 读取测试用例数量
T = int(input())

# 处理每个测试用例
for _ in range(T):
    # 读取m和n
    m, n = map(int, input().split())
    
    # 初始化一个空的最小堆
    heap = []
    
    # 读取m行，每行有n个数，并将它们添加到最小堆中
    for _ in range(m):
        row = list(map(int, input().split()))
        for num in row:
            heapq.heappush(heap, num)
    
    # 从最小堆中弹出最小的n个数，并计算它们的和
    result = sum(heapq.heappop(heap) for _ in range(n))
    
    # 输出这个和
    print(result, end=' ')