bzoj 1724 优先队列 切割木板

倒着的石子合并,注意不是取当前最长木板贪心做,而是取当前最小累加答案;

例如 4 5 6 7

若按第一种思路:ans=22+15+9

第二种:ans=22+13+9,可以先从中间某一块分开,这样答案更优

#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define ll long long
using namespace std;
const int maxn=;
inline int read(){
char ch=getchar(); int f=,x=;
while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}
while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return f*x;}
int n;ll ans;
struct node{
ll v;bool operator<(const node &b)const
{return v>b.v;}};priority_queue<node>q;
int main(){
n=read();
rep(i,,n){int x=read(); q.push((node){x});}
rep(i,,n-){
ll x=q.top().v;q.pop();
ll y=q.top().v;q.pop();
q.push((node){x+y});ans+=x+y;}
printf("%lld",ans); return ;
}
上一篇:bzoj 1724: [Usaco2006 Nov]Fence Repair 切割木板【堆】


下一篇:《JavaScript网页经典特效300例》