def find(left, right, key, num):
    while left <= right:
        mid = (left + right) // 2
        if key < num[mid]:
            right = mid - 1
        else:
            left = mid + 1
    return left

#s = input().upper()
s = 'ABCDEFABCDEFBDEFBFBFBFBBE'
n = 0
tmp = [0] * 30
word = [""] * 60
num = [0] * 60
link = [0] * 60
code = [""] * 60

# 统计频率
for letter in s:
    tmp[ord(letter) - ord("A")] += 1

# 构建频率数组
for i in range(26):
    if tmp[i]:
        word[n] = chr(65 + i)
        num[n] = tmp[i]
        n += 1

# 按频率排序
combined = sorted(zip(num[:n], word[:n]))
num[:n], word[:n] = zip(*combined)


print(combined , num, word)
# 构建哈夫曼树
n -= 1
for i in range(n):
    code[2*i] = "0"
    code[2*i+1] = "1"
    snum = num[2*i] + num[2*i+1]
    pos = find(2*i + 2, n + i, snum, num)
    # 插入新节点
    for j in range(n + i, pos - 1, -1):
        num[j+1] = num[j]
        word[j+1] = word[j]
    num[pos] = snum
    word[pos] = " "
    link[2*i] = pos
    link[2*i+1] = pos

print(link, word)

# 构建编码
for i in range(2*n):
    if word[i] != " ":
        t = link[i]
        while code[t] != " ":
            code[i] = code[t] + code[i]
            t = link[t]

# 输出结果
print("Huffman Codes:")
for i in range(2*n):
    if word[i] != " ":
        print(f"{word[i]} : {code[i]}")

本题要求计算给定 n 个叶节点权值的哈夫曼树的带权路径长度（WPL），即所有叶节点的 权值 × 路径长度 之和。

关键性质：

WPL 等于哈夫曼树中所有非叶节点的权值之和。

因为每次合并两个节点 a 和 b 生成新节点 a+b，这个 a+b 会在后续路径中被累加一次，最终总和正好是 WPL。

构造方法（基于有序数组）

我们采用一种经典的静态数组模拟法，避免使用优先队列：

初始化：将 n 个权值存入数组，并升序排序。 维护不变式：在第 i 次合并时（从 0 开始），前 2*i 个位置已被“消耗”，当前最小的两个节点一定位于 2*i 和 2*i+1。 合并：取出这两个节点，求和 merged = num[2*i] + num[2*i+1]，累加到 total。 插入：将 merged 二分插入到剩余有序部分 [2*i+2, current_size) 中，保持整体升序。 重复 n-1 次，最终 total 即为答案。

此方法时间复杂度为 O(n²)，空间 O(n)，适合 n ≤ 1000，且完全使用静态数组，符合题目要求。

C++11 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 二分查找：在 [left, right] 中找 key 应插入的位置（保持升序）
int findPos(int left, int right, int key, const vector<int>& arr) {
    while (left <= right) {
        int mid = (left + right) / 2;
        if (key < arr[mid]) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

int main() {
    int n;
    while (cin >> n) {
        vector<int> num(2000, 0); // 静态数组，最多 2*n 个节点
        for (int i = 0; i < n; ++i) {
            cin >> num[i];
        }

        // 初始排序（升序）
        sort(num.begin(), num.begin() + n);

        long long total = 0; // WPL = 所有合并产生的新节点权值之和
        int current_size = n;

        // 进行 n-1 次合并
        for (int i = 0; i < n - 1; ++i) {
            // 当前最小两个元素在 2*i 和 2*i+1
            int idx1 = 2 * i;
            int idx2 = 2 * i + 1;

            int merged = num[idx1] + num[idx2];
            total += merged;

            // 在 [2*i+2, current_size - 1] 范围内二分查找插入位置
            int pos = findPos(2 * i + 2, current_size - 1, merged, num);

            // 将 [pos, current_size) 的元素后移一位
            for (int j = current_size - 1; j >= pos; --j) {
                num[j + 1] = num[j];
            }

            // 插入新节点
            num[pos] = merged;
            current_size++;
        }

        cout << total << endl;
    }
    return 0;
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com