列表

详情

AB32. 【模板】哈夫曼编码

描述

给出一个有n种字符组成的字符串，其中第i种字符出现的次数为a_i。请你对该字符串应用哈夫曼编码，使得该字符串的长度尽可能短，求编码后的字符串的最短长度。

输入描述

第一行输入一个整数n ()，表示字符种数。
第二行输入n个整数a_i ()，表示每种字符的出现次数。

输出描述

输出一行一个整数，表示编码后字符串的最短长度。

示例1

输入: 

3
1 2 3

输出: 

9

说明:

三种字符的哈夫曼编码分别为["00","01","1"]时，长度最短，最短长度为9。

原站题解

C++ 解法, 执行用时: 68ms, 内存消耗: 2560KB, 提交时间: 2022-05-08 

#include <bits/stdc++.h>

using namespace std;
#define maxn 200000+10
#define ll long long
int n;

int main() {
    scanf("%d", & n);
    priority_queue<ll, vector<ll>, greater<ll> >q;
    ll num;
    for (int i = 0; i < n; i++) {
        scanf("%lld", & num);
        q.push(num);
    }
    ll sum = 0;
    while (!q.empty()) {
        ll a = q.top();
        q.pop();
        if (q.empty()) {
            sum += a;
        } else {
            ll b = q.top();
            q.pop();
            sum += a + b;
            if (!q.empty()) {
                q.push(a + b);
            }
        }
    }
    printf("%lld\n", sum);
    return 0;
}

C++ 解法, 执行用时: 71ms, 内存消耗: 2580KB, 提交时间: 2022-05-20 

#include<bits/stdc++.h>
using namespace std;
#define maxn 200000+10
#define ll long long 
int n;
int main(){
    scanf("%d",&n);
    priority_queue<ll ,vector<ll>,greater<ll>> q;
    ll num;
    for(int i=0;i<n;i++){
     scanf("%lld",&num);
        q.push(num);
    }
    ll sum=0;
    while(!q.empty()){
    ll a=q.top();
    q.pop();
    if(q.empty()){
    sum+=a;
    }
        else{
            ll b=q.top();
            q.pop();
            sum+=a+b;
            if(!q.empty()){
                q.push(a+b);
                }
        }
    }
    printf("%lld",sum);
    return 0;
}

C++ 解法, 执行用时: 72ms, 内存消耗: 2576KB, 提交时间: 2022-05-01 

#include <bits/stdc++.h>

using namespace std;
#define maxn 200000+10 
#define ll long long 
int n;

int main()
{
    scanf("%d",&n);
    priority_queue<ll , vector<ll>, greater<ll> >q;
    ll num;
    for(int i =0;i<n;i++)
    {
        scanf("%lld",&num);
        q.push(num);
    }
    ll sum = 0;
    while(!q.empty())
    {
        ll a = q.top();
        q.pop();
        if(q.empty())
        {
            sum+= a;
        }
        else
        {
            ll b = q.top();
            q.pop();
            sum += a+b;
            if(!q.empty())
            {
                q.push(a+b);
            }
        }
    }
    printf("%lld\n",sum);
    return 0;
}

C++ 解法, 执行用时: 72ms, 内存消耗: 2600KB, 提交时间: 2022-08-03 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    ll num;
    priority_queue<ll, vector<ll>, greater<ll>> q;
    for (int i = 0; i != n; ++i) {
        cin >> num;
        q.push(num);
    }
    ll sum = 0;
    while (!q.empty()) {
        ll a = q.top();
        q.pop();
        if (q.empty()) sum += a;
        else {
            ll b = q.top();
            q.pop();
            sum += a + b;
            if (!q.empty()) q.push(a+b);
        }
    }
    cout << sum;
    return 0;
}

C 解法, 执行用时: 84ms, 内存消耗: 1804KB, 提交时间: 2022-06-19 

#include <stdio.h>

// 方法一：底层使用小顶堆，让push和pop时间加快

void heapAdjust(long long *heap, int i, int len);
long long heapPop(long long *heap, int len) {
    if (len == 0) {
        return -1;
    }
    
    long long result = heap[0];
    
    heap[0] = heap[len - 1];
    
    heapAdjust(heap, 0, len - 1);
    
    return result;
}

void heapInsert(long long *heap, long long element, int len) {
    heap[len] = element;
    
    int child = len, parent = (len - 1) / 2;
    long long tmp;
    
    while(parent >= 0) {
        if (heap[parent] > heap[child]) {
            tmp = heap[child];
            heap[child] = heap[parent];
            heap[parent] = tmp;
            
            child = parent;
            parent = (parent - 1) / 2;
        } else {
            break;
        }
    }
}

void heapAdjust(long long *heap, int i, int len) {
    int child = 2 * i + 1, parent = i;
    long long tmp;
    
    while (child <= len - 1) {
        if (child + 1 <= len - 1 && heap[child + 1] < heap[child]) {
            child += 1;
        }
        
        if (heap[child] < heap[parent]) {
            tmp = heap[child];
            heap[child] = heap[parent];
            heap[parent] = tmp;
            
            parent = child;
            child = child * 2 + 1;
        } else {
            break;
        }
    }
}

void heapInit(long long *heap, int len) {
    int lastParent = (len - 2) / 2;
    
    for (int i = lastParent; i >= 0; i--) {
        heapAdjust(heap, i, len);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    
    long long *heap = (long long *)malloc(sizeof(long long) * n);
    int i = 0;
    while(i < n) {
        scanf("%lld", &heap[i]);
        i++;
    }
    
    heapInit(heap, n);
    
    int count = 0;
    
    long long sumCount = 0, m1, m2, newA = 0;
    
    while(count < n - 1) {
        m1 = heapPop(heap, n - count);
        m2 = heapPop(heap, n - count - 1);
        newA = m1 + m2;
        sumCount += newA;
        heapInsert(heap, newA, n - count - 2);

        count++;
    }
    
    if (n == 1) {
        sumCount = heapPop(heap, n);
    }
    
    printf("%lld", sumCount);
    
    return 0;
}







// 方法二：底层使用有序连续数组+二分插入排序，时间总是超时
// void quickSort(int *a, int start, int end) {
//     if (start < end) {
//         int rIndex = rand() % (end - start + 1) + start, tmp;
//         tmp = a[rIndex];
//         a[rIndex] = a[start];
//         a[start] = tmp;

//         int target = a[start], i = start, j = end;
//         while(i < j) {
//             while(i < j && a[j] > target) {
//                 j--;
//             }
//             if(i < j) {
//                 a[i++] = a[j];
//             }
//             while(i < j && a[i] <= target) {
//                 i++;
//             }
//             if(i < j) {
//                 a[j--] = a[i];
//             }
//         }
        
//         a[i] = target;
        
//         quickSort(a, start, i - 1);
//         quickSort(a, i + 1, end);
//     }
// }

// int cmp(const void *a, const void *b) {
//     return *((int *)a) - *((int *)b);
// }

// int main() {
//     int n;
//     scanf("%d", &n);
    
//     int *a = (int *)malloc(sizeof(int) * n);
//     int i = 0;
//     while(i < n) {
//         scanf("%d", &a[i]);
//         i++;
//     }
    
//     qsort(a, n, sizeof(int), cmp);
//     //quickSort(a, 0, n - 1);
    
//     i = 0;
    
//     int sumCount = 0, newA = 0, left, right, mid, lastRight, j;
    
//     while(i < n - 1) {
//         a[i+1] = a[i] + a[i+1];
//         sumCount += a[i+1];

//         qsort(a + i + 1, n - i - 1, sizeof(int), cmp);
        
// //         newA = a[i+1];
        
// //         left = i + 2;
// //         right = n - 1;
// //         lastRight = n;
// //         while(left <= right) {
// //             mid = (left + right) / 2;
// //             if (a[mid] >= newA) {
// //                 lastRight = mid;
// //                 right = mid - 1;
// //             } else {
// //                 left = mid + 1;
// //             }
// //         }
        
// //         for (j = i + 2; j < lastRight; j++) {
// //             a[j-1] = a[j];
// //         }
// //         a[lastRight - 1] = newA;
        
//         i++;
//     }
    
//     if (n == 1) {
//         sumCount = a[0];
//     }
    
//     printf("%d", sumCount);
    
//     return 0;
// }

上一题

© 2025 nowcoder.com