BZOJ4198: [Noi2015]荷马史诗(哈夫曼树)
2018-07-06 01:20:06来源:博客园 阅读 ()
Submit: 1824 Solved: 983
[Submit][Status][Discuss]
Description
追逐影子的人,自己就是影子。 ——荷马
Input
输入文件的第 1 行包含 2 个正整数 n,k,中间用单个空格隔开,表示共有 n 种单词,需要使用 k 进制字符串进行替换。
Output
输出文件包括 2 行。
Sample Input
1
1
2
2
Sample Output
2
HINT
Source
把出现次树看做是点权,长度看做是点到根的路径长度
这个问题就转化成了哈夫曼树问题,不过是在$k$进制下的。
因此用有限队列维护,每次弹出前$k$个元素就好了
注意n-1 \pmod k-1 \not = 0$的时候需要补零
传说还有线性的算法?算了不学了
#include<cstdio> #include<vector> #include<algorithm> #include<cstring> #include<map> #include<cmath> #include<queue> #define int long long using namespace std; const int INF = 1e9 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, K; struct Node { int w, h; bool operator < (const Node &rhs) const{ return w == rhs.w ? h > rhs.h : w > rhs.w; } }; priority_queue<Node> q; main() { N = read(); K = read(); for(int i = 1; i <= N; i++) q.push((Node){read(), 1}); int tot = N, ans = 0; if((N - 1) % (K - 1) != 0) tot += K - 1 - ((N - 1) % (K - 1)); for(int i = 1; i <= tot - N; i++) q.push((Node) {0, 1}); while(tot > 1) { int val = 0, mxh = 0; for(int i = 1; i <= K; i++) { Node top = q.top(); q.pop(); val += top.w; mxh = max(mxh, top.h); } ans += val; q.push((Node){val, mxh + 1}); tot -= K - 1; } printf("%lld\n%lld", ans, q.top().h - 1); }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- BZOJ4008: [HNOI2015]亚瑟王(期望dp) 2018-07-11
- BZOJ4196: [Noi2015]软件包管理器(树链剖分 线段树) 2018-07-09
- BZOJ4195: [Noi2015]程序自动分析(并查集) 2018-07-06
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash