[NOI2015] 荷马史诗

GitHub跳转原题关系图返回列表

补零后执行 K 叉 Huffman 合并，堆中同时维护权重与子树高度。

OJ: luogu

题目 ID: P2168

难度:提高+/省选-

标签:K叉Huffman贪心heapqpython

日期: 2026-07-16 21:00

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

构造最优 K 进制前缀编码，先最小化加权总长度，再最小化最大码长。

思路

K 叉 Huffman 每次合并最小的 K 个权重。完整 K 叉树叶数满足 (leaf-1) % (K-1)==0，不足时补权重 0 的虚叶。

堆元素为 (weight, depth)。合并费用增加所选权重和，新节点高度是最大子高度加一；元组在权重相同时优先较小高度，得到第二关键字最优。

Python 知识

  • 元组由左到右比较，天然实现两级优先级。
  • 列表推导式连续 heappop K 次。
  • heapq.heapify 线性建堆。

代码

python
import heapq
import sys


data = iter(map(int, sys.stdin.buffer.read().split()))
n, base = next(data), next(data)
heap = [(next(data), 0) for _ in range(n)]
padding = (base - 1 - (n - 1) % (base - 1)) % (base - 1)
heap.extend([(0, 0)] * padding)
heapq.heapify(heap)
total_cost = 0

while len(heap) > 1:
    chosen = [heapq.heappop(heap) for _ in range(base)]
    weight = sum(item[0] for item in chosen)
    depth = max(item[1] for item in chosen) + 1
    total_cost += weight
    heapq.heappush(heap, (weight, depth))

print(total_cost)
print(heap[0][1])

复杂度

时间 O(nlog⁡n)O(n\log n)，空间 O(n)O(n)。

总结

K 叉 Huffman 相比二叉版多了“补零使叶数合法”和“同权重按高度决策”两个细节。