题解 P1334 【瑞瑞的木板】

· · 题解

相信许多人都已经知道了这道题就是合并果子，但是还不知道它是怎样转化成合并果子的，我觉得楼下的dalao们都讲的不太清楚，这里我给大家举个例子：

比如说9 7 6 5 3,有些同学可能会想：每次我砍最大的，然后剩下的不就少了。其实不然，因为不一定一次只能砍一个，可以砍两个或两个以上。不多说，我把上面例子的最优策略讲出来大概就知道了。

step1：把9+7+6+5+3切成7+6和5+3+9两部分；
step2：把7+6切成7和6；
step3：把5+3+9切成5+3和9两部分：
step4：把5+3切成5和3。

这时我们再回过头来看，是不是就是合并果子的步骤？

代码如下：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
priority_queue<ll,vector<ll>,greater<ll> > a;//这里直接调用优先队列
#define in(t) freopen("t.in","r",stdin)
#define out(t) freopen("t.out","w",stdout)
#define m(a) memset(a,0,sizeof(a))
int main(){
    long long ans=0,n,t;//ans注意要开long long,不然会爆
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&t);
        a.push(t);
    }
    for(int i=1;i<=n-1;i++){
        int c,d;
        c=a.top();
        a.pop();
        d=a.top();
        a.pop();//每次取最小的两个数
        ans+=c+d;//加上能量
        a.push(c+d);
}//和合并果子一样，具体可以参考合并果子题解
    printf("%lld",ans);

    return 0;

}