相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4198
解题报告
k叉哈夫曼树
注意最大化儿子不满的那个结点的深度
Code
#include<bits/stdc++.h> #define LL long long using namespace std; struct Data{ LL apt, mx; inline Data() { } inline Data(LL a, LL c):apt(a), mx(c) { } inline Data operator + (const Data &d) { return Data(apt + d.apt, max(mx, d.mx + 1)); } inline bool operator < (const Data &d) const { return apt > d.apt || (apt == d.apt && mx > d.mx); } }; priority_queue<Data> que; inline LL read() { char c=getchar(); LL ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } int main() { int n = read(), k = read(); for (int i = 1; i <= n; i++) { que.push(Data(read(), 0)); } LL ans = 0; for (bool frt = (n - 1) % (k - 1); (int)que.size() > 1; frt = 0) { Data np(0, 0); for (int i = frt? 1 + (n - 1) % (k - 1): k; i; --i) { np = np + que.top(); que.pop(); } ans += np.apt; que.push(np); } printf("%lld\n%lld\n", ans, que.top().mx); return 0; }
Fantastic article.Really thank you! Cool.
Really informative blog. Great.
I cannot thank you enough for the blog article.Thanks Again. Much obliged.
Thank you for your blog article.Much thanks again. Much obliged.
Thanks-a-mundo for the blog post.Much thanks again. Will read on…
Looking forward to reading more. Great article post.Really thank you! Will read on…
Major thankies for the blog post. Great.
I value the post.Really thank you! Cool.
Im obliged for the article post.Thanks Again. Will read on…
Appreciate you sharing, great blog post.Much thanks again. Much obliged.
I value the article. Really Great.
Thank you ever so for you article post.Much thanks again. Want more.
Wow, great blog.Really thank you!
Really informative blog article.Really looking forward to read more. Much obliged.
Wow, great article post.Really looking forward to read more. Keep writing.
Really appreciate you sharing this blog. Fantastic.
I cannot thank you enough for the blog.Really looking forward to read more. Cool.
Wow, great article post.Really looking forward to read more. Keep writing.
I really liked your article. Really Great.
Major thankies for the blog article.Thanks Again. Keep writing.
Fantastic article post.Really thank you! Fantastic.
Thank you for your blog post.Much thanks again. Much obliged.
Great, thanks for sharing this article post.Thanks Again. Cool.
Im grateful for the blog post.Really looking forward to read more. Really Great.
Thanks again for the article.Really looking forward to read more. Keep writing.
Thanks so much for the article.Really thank you!
Im grateful for the blog post. Great.
Thanks for the post.Really looking forward to read more.
Enjoyed every bit of your blog post.Really thank you!
Great, thanks for sharing this blog post.Thanks Again.
Thanks again for the blog article.Really thank you! Much obliged.
Appreciate you sharing, great post.Really thank you! Great.
Muchos Gracias for your blog.Really looking forward to read more. Want more.
Enjoyed every bit of your blog. Really Cool.
Major thanks for the article.Really looking forward to read more. Great.
Im grateful for the article.Thanks Again. Really Cool.
I really liked your article post.Really looking forward to read more. Keep writing.
Major thankies for the post.Really thank you! Awesome.
This is one awesome article.Much thanks again. Much obliged.
Muchos Gracias for your article.Much thanks again. Awesome.
I have not checked in here for some time because I thought it was getting boring, but the last few posts are great quality so I guess I?¦ll add you back to my daily bloglist. You deserve it my friend 🙂
Great, thanks for sharing this article.Really looking forward to read more. Much obliged.
I really enjoy the blog post.Really looking forward to read more.
Thank you ever so for you article post.Much thanks again. Really Great.
wow, awesome blog.Much thanks again. Awesome.
Thanks for the blog article.Really looking forward to read more. Much obliged.
I think this is a real great blog.Thanks Again. Awesome.
I value the article. Really Great.
Very informative blog. Want more.
Appreciate you sharing, great article.Really thank you! Much obliged.
Wow, great blog.Really looking forward to read more. Really Great.
Thanks again for the article. Keep writing.
Thanks again for the post.Much thanks again. Want more.
Wow, great article.Much thanks again. Really Cool.
A round of applause for your post.
I really enjoy the article.Really thank you! Really Great.
Im thankful for the blog article. Cool.
A round of applause for your article post.Really thank you! Much obliged.
I cannot thank you enough for the blog.Really looking forward to read more. Really Great.
I appreciate you sharing this blog article.Really thank you! Cool.
I cannot thank you enough for the blog post.Thanks Again. Awesome.
wow, awesome article post.Really thank you! Fantastic.
I really liked your article post.Really thank you! Will read on…
Im obliged for the article post.Thanks Again. Fantastic.
I appreciate you sharing this post.Much thanks again. Really Great.
Looking forward to reading more. Great blog post.Thanks Again.
Looking forward to reading more. Great post.Much thanks again. Will read on…
I really enjoy the article.Really thank you!
Really enjoyed this blog post.Thanks Again. Awesome.
Im obliged for the post.Much thanks again. Really Great.
I really liked your post.Really looking forward to read more. Great.
Thanks a lot for the post.Really looking forward to read more. Awesome.
I truly appreciate this blog article.Much thanks again. Want more.
This is one awesome blog.Really looking forward to read more. Want more.
Wow, great article post. Much obliged.
I cannot thank you enough for the blog article.Thanks Again. Will read on…
Major thanks for the article.Really thank you! Awesome.
Thanks so much for the article.Much thanks again. Want more.
A big thank you for your blog post.Thanks Again. Really Cool.
I really enjoy the post.Really thank you! Awesome.
Muchos Gracias for your post.Really looking forward to read more. Fantastic.
Thanks-a-mundo for the article post.Really looking forward to read more. Cool.
Enjoyed every bit of your article. Keep writing.
Major thankies for the post.Much thanks again. Much obliged.
I really liked your article post.Much thanks again.
I truly appreciate this article post.Much thanks again. Fantastic.
I value the post.Thanks Again. Keep writing.
Major thanks for the post.Much thanks again. Cool.
Thank you ever so for you article post.Really looking forward to read more. Great.
I loved your article post.Really looking forward to read more. Great.
I loved your blog article.Really looking forward to read more. Awesome.
Thanks so much for the blog post.Really thank you! Cool.
Thanks for sharing, this is a fantastic blog post.Much thanks again. Great.
Really appreciate you sharing this post.Really thank you! Fantastic.
Thanks-a-mundo for the article.Thanks Again. Cool.
A round of applause for your blog article.Really thank you! Great.
I cannot thank you enough for the post.Really looking forward to read more. Keep writing.
Major thankies for the blog post.Really thank you! Fantastic.
Looking forward to reading more. Great article.Really thank you! Fantastic.
Enjoyed every bit of your article post.Really thank you! Want more.
Really informative blog post.Really looking forward to read more. Cool.
Thanks so much for the blog article.Much thanks again. Much obliged.
Thanks for the blog post.Really looking forward to read more. Awesome.
I really liked your blog post. Much obliged.
This is one awesome blog. Awesome.
Very good blog. Keep writing.
Thanks a lot for the blog article. Really Cool.
Really enjoyed this blog.Really looking forward to read more. Want more.
Awesome article post. Great.
A big thank you for your post.Thanks Again. Fantastic.
I really enjoy the article post.Really looking forward to read more. Awesome.
I wanted to thank you for this great read!! I definitely enjoying every little bit of it I have you bookmarked to check out new stuff you post…
Really appreciate you sharing this blog. Will read on…
I appreciate you sharing this article. Really Cool.
Great, thanks for sharing this post.Really thank you! Cool.
Very good blog post.Really looking forward to read more. Awesome.
Thank you ever so for you blog.Really thank you! Will read on…
Major thanks for the blog.Thanks Again. Awesome.
This is one awesome blog.Really thank you!
I really liked your article post.Thanks Again. Really Cool.
I really enjoy the blog post.Thanks Again. Keep writing.
Fantastic blog post.Really looking forward to read more. Awesome.
I really like and appreciate your blog.Much thanks again. Awesome.
A big thank you for your blog article.Much thanks again. Really Cool.
Say, you got a nice blog article.Really thank you! Want more.
Major thankies for the blog post.Really thank you! Great.
Great, thanks for sharing this post.Really looking forward to read more. Fantastic.
Major thankies for the article post.Really thank you! Will read on…
I appreciate you sharing this article post. Keep writing.
I think this is a real great article post.Really thank you! Really Great.
Thank you for your blog post.Really thank you! Really Great.
A big thank you for your blog.Really thank you! Cool.
I loved your article post.Really looking forward to read more. Really Great.
This is one awesome article post.Much thanks again. Fantastic.
Really informative article post.Really thank you! Awesome.
Awesome blog.Much thanks again. Keep writing.
Thanks again for the blog post.Really thank you! Much obliged.
Awesome blog post.Really looking forward to read more. Much obliged.
Very informative post.Really looking forward to read more. Much obliged.
Really enjoyed this blog article. Keep writing.
I truly appreciate this article post.Really looking forward to read more.
Say, you got a nice article.Much thanks again. Will read on…
Thanks for sharing, this is a fantastic post.Much thanks again. Awesome.
This is one awesome blog post.Really thank you! Want more.
Major thankies for the blog article.
Major thanks for the post. Cool.
I really like and appreciate your blog post.Really looking forward to read more. Keep writing.
Hey, thanks for the article.Really looking forward to read more. Cool.
Very informative article. Really Cool.
I truly appreciate this article.Much thanks again. Really Great.