【输入格式】有两行 • 第一行为整数n (1 <= n <= 50000)。 • 第二行为用空格分开的n个正整数w1,…,wn，每个在[1,4000] 【输出格式】一个整数，表示w1,…,wn的哈夫曼树的WPL。 (WPL=weighted path length=带权路径长度）用c++实现，且不用算法库，先用O(nlogn)算法排序，然后利用递增特性累加计算WPL

好的，我明白了。这是一个经典的哈夫曼树问题，我会用C++实现一个解决方案。

首先，我们需要定义一个哈夫曼树节点的结构体，包含权值和左右子节点指针。代码如下：

struct Node {
    int val;
    Node *left, *right;
    Node(int v): val(v), left(NULL), right(NULL) {}
};

接下来，我们需要实现一个比较函数，用于在排序时按照权值从小到大排序。代码如下：

bool cmp(int a, int b) {
    return a < b;
}

然后，我们可以将输入的权值数组按照权值从小到大排序。代码如下：

sort(w, w + n, cmp);

接下来，我们可以开始构建哈夫曼树。我们从权值最小的两个节点开始，将它们合并成一个新节点，权值为两个节点的权值之和。然后将这个新节点插入到权值数组中，并把它们从数组中删除。我们不断重复这个过程，直到只剩下一个节点为止。最后这个节点就是哈夫曼树的根节点。

下面是代码实现：

Node* buildHuffmanTree(int* w, int n) {
    priority_queue<int, vector<int>, greater<int>> q; // 小根堆
    for (int i = 0; i < n; i++) {
        q.push(w[i]);
    }
    while (q.size() > 1) {
        int a = q.top();
        q.pop();
        int b = q.top();
        q.pop();
        q.push(a + b);
    }
    Node* root = new Node(q.top());
    return root;
}

最后，我们需要计算哈夫曼树的带权路径长度。我们可以用递归的方式计算每个节点的带权路径长度，然后把它们累加起来。代码如下：

int calcWPL(Node* root, int depth) {
    if (!root->left && !root->right) {
        return root->val * depth;
    }
    int sum = 0;
    if (root->left) sum += calcWPL(root->left, depth + 1);
    if (root->right) sum += calcWPL(root->right, depth + 1);
    return sum;
}

完整代码如下：

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

struct Node {
    int val;
    Node *left, *right;
    Node(int v): val(v), left(NULL), right(NULL) {}
};

bool cmp(int a, int b) {
    return a < b;
}

Node* buildHuffmanTree(int* w, int n) {
    priority_queue<int, vector<int>, greater<int>> q; // 小根堆
    for (int i = 0; i < n; i++) {
        q.push(w[i]);
    }
    while (q.size() > 1) {
        int a = q.top();
        q.pop();
        int b = q.top();
        q.pop();
        q.push(a + b);
    }
    Node* root = new Node(q.top());
    return root;
}

int calcWPL(Node* root, int depth) {
    if (!root->left && !root->right) {
        return root->val * depth;
    }
    int sum = 0;
    if (root->left) sum += calcWPL(root->left, depth + 1);
    if (root->right) sum += calcWPL(root->right, depth + 1);
    return sum;
}

int main() {
    int n;
    cin >> n;
    int w[50000];
    for (int i = 0; i < n; i++) {
        cin >> w[i];
    }
    sort(w, w + n, cmp);
    Node* root = buildHuffmanTree(w, n);
    int wpl = calcWPL(root, 0);
    cout << wpl << endl;
    return 0;
}

希望这个解决方案可以帮到你！