蓝桥545.谈判 ​

题目 ​

1.谈判 - 蓝桥云课

题目描述 ​

在很久很久以前，有 $n$ 个部落居住在平原上，依次编号为 $1$ 到 $n$。第 $i$ 个部落的人数为 $t_i$。

有一年发生了灾荒。年轻的政治家小蓝想要说服所有部落一同应对灾荒，他能通过谈判来说服部落进行联合。

每次谈判，小蓝只能邀请两个部落参加，花费的金币数量为两个部落的人数之和，谈判的效果是两个部落联合成一个部落（人数为原来两个部落的人数之和）。

求最小的总花费。

输入描述 ​

输入的第一行包含一个整数 $n$，表示部落的数量。

第二行包含 $n$ 个正整数，依次表示每个部落的人数。

其中，$1\le n\le 1000$，$1\le t_i\le {10}^4$。

输出描述 ​

输出一个整数，表示最小花费。

示例 ​

输入：

4
9 1 3 5

输出：

31

题解 ​

这个问题可以通过贪心算法来解决。具体来说，我们每次合并当前人数最少的两个部落，这样可以确保每次合并的花费最小。通过不断合并，直到只剩下一个部落为止，这样可以得到总的最小花费。

为了高效地获取当前人数最少的两个部落，可以使用最小堆来维护部落的人数。每次从堆中取出两个最小的元素进行合并，并将合并后的新部落人数放回堆中，同时累加合并的花费。

import heapq

n = int(input())
t = list(map(int, input().split()))

# 使用优先队列（最小堆）来维护部落人数
heapq.heapify(t)
total_cost = 0

while len(t) > 1:
    # 取出两个最小的部落
    a = heapq.heappop(t)
    b = heapq.heappop(t)
    # 计算合并花费
    cost = a + b
    total_cost += cost
    # 将合并后的新部落放回堆中
    heapq.heappush(t, cost)

print(total_cost)

1. 使用 heapq 模块来实现最小堆。

2. 将输入的部落人数列表转换为堆结构。

3. 每次从堆中取出两个最小的元素，计算合并花费，并将合并后的新部落人数放回堆中。

4. 累加所有合并的花费，直到只剩下一个部落。

5. 时间复杂度为 $O(n\log n)$