首页 / 算法 / ｐｏｊ ３２５３（贪心）
ｐｏｊ ３２５３（贪心）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了ｐｏｊ ３２５３（贪心），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含974字，纯文字阅读大概需要2分钟。
内容图文
http://poj.org/problem?id=3253
题意：就是一个木头要做成栏杆，所以要进行切割，每一次所需要的费用就等于切割的木头的长度，求最少的费用。
思路： 这一个是霍夫曼编码的题？我最开始真的没看出来，我一直都以为是贪心，最开始想的也挺简单的。就是减，每次减个最大的木头的长度就可以了，然后WA了几次，我还以为是我的优先队列用错的了，然后用快排写，还是wa，最后还是别人和我说了下他的思路，我才发现我理解是错了，每次切割不一定要切割的是所需的长度中最长的，而应该是把木板切成一块一块，然后再从这一块一块中来切，这样的钱才是最少的。
1 #include <stdio.h>
2 #include <string.h>
3 #include <vector>
4 #include <queue>
5 6usingnamespace std;
7int main()
8 {
9// freopen("in.txt","r",stdin); 10 priority_queue<int,vector<int>,greater<int> >s;
11int n,tmp,tmp1;
12longlong ans = 0;
13 scanf("%d",&n);
14for(int i=0;i<n;i++)
15 {
16 scanf("%d",&tmp);
17 s.push(tmp);
18 }
19 20// ans += a[0]; 21for(int i=0;i<n-1;i++) //对两个最小的进行合并，然后在相加，在入队列，这里不能暴力，会TLE。
22 {
23 tmp =s.top();
24 s.pop();
25 tmp1=s.top();
26 s.pop();
27 ans += tmp+ tmp1;
28 tmp1 += tmp;
29 s.push(tmp1);
30 }
31 printf("%lld\n",ans);
32return 0;
33 }
原文：http://www.cnblogs.com/Tree-dream/p/5747472.html
内容总结
以上是互联网集市为您收集整理的ｐｏｊ ３２５３（贪心）全部内容，希望文章能够帮你解决ｐｏｊ ３２５３（贪心）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。