[编程题-美团] 字符编码

[编程题] 字符编码

请设计一个算法，给一个字符串进行二进制编码，使得编码后字符串的长度最短。

输入描述:

每组数据一行，为待编码的字符串。保证字符串长度小于等于1000。

输出描述:

一行输出最短的编码后长度。

输入例子:

MT-TECH-TEAM

输出例子:

33

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;
int main(){
    char s[3300];
    while(scanf("%s",s) != EOF){
        int n = strlen(s);
        sort(s,s + n);
        priority_queue<int> heap;//priority_queue 默认是 大顶堆
        int cnt = 0;
        for(int i = 0,j;i < n;){
            j = i;
            while(j < n && s[j] == s[i]) ++ j;
            heap.push(i - j);
            i = j;
            ++ cnt;
        }
        int ret = 0;
        for(int i = 0;i < cnt - 1;++ i){
            int A = heap.top(); heap.pop();
            int B = heap.top(); heap.pop();
            ret -= A + B;
            heap.push(A + B);
        }  
        printf("%d
",ret);
    }
    return 0;
}