这道题算最短的编码,因此我们采用构造哈夫曼树。首先我们先解析出一行字符串里每个字符的出现次数,用std::map 进行保存。然后我们使用队列来构造哈夫曼树。
#include <algorithm> #include <cmath> #include <cstdint> #include <exception> #include <functional> #include <iostream> #include <iterator> #include <map> #include <memory> #include <ostream> #include <stack> #include <vector> class StrEncode { struct haff_node_t { int weight; bool is_leaf; char data; int height = 0; std::shared_ptr<haff_node_t> left, right; haff_node_t(haff_node_t& node) { weight = node.weight; is_leaf = node.is_leaf; data = node.data; left = node.left; right = node.right; } explicit haff_node_t(int weight, bool is_leaf = false, char data = '\0') : weight(weight), is_leaf(is_leaf), data(data) {} explicit haff_node_t(const std::pair<char, int>& p) { this->data = p.first; this->weight = p.second; this->is_leaf = true; } bool operator<(const haff_node_t& node) const { return this->weight < node.weight; } bool operator>(const haff_node_t& node) const { return this->weight > node.weight; } bool operator==(const haff_node_t& node) const { return this->data == node.data; } bool operator==(const char& c) const { return this->data == c; } bool static cmp_greater(const haff_node_t& n1, const haff_node_t& n2) { return n1 > n2; } static bool cmp_greater_inptr( const std::shared_ptr<haff_node_t>& n1, const std::shared_ptr<haff_node_t>& n2) { if (n1.get() && n2.get()) { return n1->weight > n2->weight; } throw std::runtime_error("pointers are null"); } }; public: static void solve(const std::string& line) { std::map<char, int> mp; int min_encode_len = 0; for (const auto& c : line) { if (mp.find(c) == mp.end()) { mp[c] = 1; } else { mp[c]++; } } std::vector<std::shared_ptr<haff_node_t>> node_vec; node_vec.reserve(mp.size()); for (auto& m : mp) { node_vec.push_back(std::make_shared<haff_node_t>(m)); } std::sort( node_vec.begin(), node_vec.end(), haff_node_t::cmp_greater_inptr); while (node_vec.size() > 1) { auto right = node_vec.back(); node_vec.pop_back(); auto left = node_vec.back(); node_vec.pop_back(); auto new_node = std::make_shared<haff_node_t>( right->weight + left->weight); new_node->left = left; new_node->right = right; node_vec.push_back(new_node); if (!new_node->is_leaf) { min_encode_len += new_node->weight; } std::sort( node_vec.begin(), node_vec.end(), haff_node_t::cmp_greater_inptr); } std::cout << min_encode_len << std::endl; } }; int main() { std::string line; while (getline(std::cin, line)) { // 注意 while 处理多个 case StrEncode::solve(line); } } // 64 位输出请用 printf("%lld")