BZOJ 1724 [Usaco2006 Nov]Fence Repair 切割木板:贪心 优先队列【合并果子】

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1724

题意:

  你要将一块长木板切成n段,长度分别为a[i](长木板的长度 = ∑ a[i])。

  每一次切割的花费为被切割木板的长度。

  问你切完的最小花费。

题解:

  合并果子。

  反过来想:切割 = 合并

  贪心策略:每次选目前所有堆中最小的两个合并。(尽可能少移动大的果子堆)

  实现:优先队列

AC Code:

 #include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue> using namespace std; int n;
long long ans=;
priority_queue<int,vector<int>,greater<int> > q; int get_top()
{
int now=q.top();
q.pop();
return now;
} int main()
{
cin>>n;
int a;
for(int i=;i<n;i++)
{
cin>>a;
q.push(a);
}
while(q.size()>)
{
int v1=get_top();
int v2=get_top();
ans+=v1+v2;
q.push(v1+v2);
}
cout<<ans<<endl;
}
上一篇:1724: [Usaco2006 Nov]Fence Repair 切割木板( 贪心 )


下一篇:[Usaco2006 Nov] Fence Repair 切割木板