首页 > 代码库 > bzoj1724[Usaco2006 Nov]Fence Repair 切割木板*
bzoj1724[Usaco2006 Nov]Fence Repair 切割木板*
bzoj1724[Usaco2006 Nov]Fence Repair 切割木板
题意：
FJ需要n块木板，第i块木板长度为ai。但他只有一块长度为sigma(i,1,n)ai的木板。每切一次的代价为所切割木板的长度，问最小代价。n≤20000
题解：
等价于合并石子（把单块木板的长度看作石子）。故用一个优先队列，每次找最小的两个堆合并起来再放入优先队列，代价计入答案。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 20010 7 #define ll long long 8 using namespace std; 9 10 inline int read(){11 char ch=getchar(); int f=1,x=0;12 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}13 while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();14 return f*x;15 }16 int n; ll ans;17 struct nd{ll a; bool operator < (const nd &b)const{return a>b.a;}}; priority_queue<nd>q;18 int main(){19 n=read(); inc(i,1,n){int x=read(); q.push((nd){x});}20 inc(i,1,n-1){ll x=q.top().a; q.pop(); ll y=q.top().a; q.pop(); q.push((nd){x+y}); ans+=x+y;}21 printf("%lld",ans); return 0;22 }
20160917
bzoj1724[Usaco2006 Nov]Fence Repair 切割木板*
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。