acwing::acwing149 命名空间参考

1. 荷马史诗

更多...

类
struct	Compare
class	huff_tree

函数
int	main (istream &cin, ostream &cout)
	TEST (acwing149, case1)
	TEST (acwing149, case2)
	TEST (acwing149, case3)

详细描述

1. 荷马史诗

函数说明

main()

int acwing::acwing149::main	(	istream &	cin,
		ostream &	cout
	)

在文件 acwing408.cpp 第 536 行定义.

                                              {
            u_int64_t n, k, w;
            cin >> n >> k;
            priority_queue<huff_tree *, vector<huff_tree *>, Compare> pq;
            for(int i = 0; i < n; i++) {
                cin >> w;
                pq.push(new huff_tree(w, 1, k));
            }
            while((n - 1) % (k - 1)) {
                pq.push(new huff_tree(0, 1, k));
                n++;
            }
            while(pq.size() > 1) {
                huff_tree *ht = new huff_tree(0, 0, k);
                for(int i = 0; i < k && !pq.empty(); i++) {
                    huff_tree *least = pq.top();
                    ht->height       = max(ht->height, least->height + 1);
                    ht->children[i]  = least;
                    ht->val += least->val;
                    pq.pop();
                }
                pq.push(ht);
            }
            huff_tree *root = pq.top();
            queue<pair<huff_tree *, u_int64_t>> q;
            q.push(make_pair(root, 0));
            u_int64_t min_level = 0;
            u_int64_t sum       = 0;
            while(!q.empty()) {
                auto [ht, level] = q.front();
                q.pop();
                bool flag = true;
                for(int i = 0; i < k; i++) {
                    if(ht->children[i] != nullptr) {
                        flag = false;
                        q.push(make_pair(ht->children[i], level + 1));
                    }
                }
                if(flag) {
                    sum += ht->val * level;
                    min_level = max(min_level, level);
                }
            }
            cout << sum << endl
                 << min_level << endl;
            return 0;
        }

引用了 acwing::acwing149::huff_tree::children, acwing::acwing149::huff_tree::height, acwing::acwing3786::root, acwing::TreeNode::val , 以及 acwing::acwing149::huff_tree::val.

被这些函数引用 TEST().

TEST() [1/3]

acwing::acwing149::TEST	(	acwing149	,
		case1
	)

在文件 acwing408_test.cpp 第 1023 行定义.

                               {
            istringstream in("4 2\n"
                             "1\n"
                             "1\n"
                             "2\n"
                             "2");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("12\n"
                      "2\n",
                      ans);
        }

引用了 main().

TEST() [2/3]

acwing::acwing149::TEST	(	acwing149	,
		case2
	)

在文件 acwing408_test.cpp 第 1037 行定义.

                               {
            istringstream in("3 2\n"
                             "1\n"
                             "2\n"
                             "3");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("9\n"
                      "2\n",
                      ans);
        }

引用了 main().

TEST() [3/3]

acwing::acwing149::TEST	(	acwing149	,
		case3
	)

在文件 acwing408_test.cpp 第 1050 行定义.

                               {
            istringstream in("16 3\n"
                             "98\n"
                             "98\n"
                             "98\n"
                             "98\n"
                             "98\n"
                             "98\n"
                             "98\n"
                             "98\n"
                             "98\n"
                             "98\n"
                             "98\n"
                             "98\n"
                             "98\n"
                             "98\n"
                             "98\n"
                             "98");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("4214\n"
                      "3\n",
                      ans);
        }

引用了 main().