看题传送门::http://poj.org/problem?id=3253
题目大意:
给定n个小木板的长度,一个农夫要把一个无限长的木板锯成给定的目标,每一次锯的长度就是费用,求最小费用。
hints:
目标长度为:8 5 8
起初的木板长度为8+5+8=21
第一切将会花费21 ,将 切为13 和 8 两块。
第二次将会花费13 ,将13那块切为 8 和 5 两块。
贪心算法。
一开始想错,以为每次切掉最长的,其实不然,没有理解题意。
其实题目说的是每次切掉部分的两块的和才为费用。
dicuss里有大神的关于Huffman树的思路“
我们不妨将切木板的过程反过来看,也就是将所有切好了的木板每次拿两块拼接起来(每次拼接后的长度就是费用),最终便会拼接成原来的完整的木板。显然,这个过程是Huffman编码过程,且正过程和逆过程费用相同”
所以利用这个思想,每次选取最短的两个木板,构成新的木板,并重新插入优先队列中。
用到了STL的优先队列
#include<cstdio>
#include<queue>
using namespace std;
const int MAXN=50000+10;
struct data
{
__int64 need;
bool operator <(const data& p)const
{
return need > p.need;
}
};
priority_queue<data> q;
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
data s;
for(int i=0;i<n;i++)
{
scanf("%I64d",&s.need);
q.push(s);
}
__int64 ans=0;
while(q.size()>1 )
{
int k1=q.top().need;
q.pop();
int k2=q.top().need;
q.pop();
data temp;
temp.need=k1+k2;
ans+=temp.need;
q.push(temp);
}
printf("%I64d\n",ans);
while(!q.empty()) //清空队列
q.pop();
}
}