题解 P1334 【瑞瑞的木板】

· · 题解

瑞瑞的木板(拆分果子)

大家先去看看这道题。

发现了什么？

什么都没有

观察发现，合并果子就是将一堆果子从小到大合并，运用了哈夫曼树的思想。

这题呢？

它是问你将一块木板不断拆分，既能拆成所有需要的长度，消耗能量也最少。

有什么关联？

首先，拆分的时候是先将所需要的最大的长度拆分出来，再继续拆剩下的，直到都拆分完毕，这样就是消耗能量最小的方案。

是不是有点像了？

再继续。

我们可以运用逆向思维，从最小的长度开始，不断合并第一个比它大的长度，将拆分的过程反过来推，消耗的能量跟正推也是一样的。

SO？

不就是合并果子裸题啰。

怎么实现？

如果你一个一个合并，再把合并后的长度放入原数组，再重新排序，不仅实现难度大，而且时间爆炸。

怎么做？

观察数据范围，n≤10000,O(n^2)都是玄学。

当然O(n\log{n})最有可能啰。

再观察解题思路，你会发现需要不停地动态取最小值。

加粗字让你想到了什么？

那不就是堆吗。

用小根堆来存储每次合并后的所需木板长度，每次直接从堆顶取出两个最小值，合并后再放入堆中，直到堆里只有一个元素。

时间复杂度完完美美O(n\log{n})。

AC$ $Code 
#include <iostream>
#include <queue>//STL是个好东西
using namespace std;

priority_queue<int, vector<int>, greater<int> > pq;//小根堆标准定义
int a[1000010],n;
long long ans;//注意最终答案会爆int!要用long long存！

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pq.push(a[i]);
    }//输入+预处理
    for(int i=1;i<=n-1;i++){
        int a=pq.top();//取出最小元素
        pq.pop();
        int b=pq.top();//取出第二小元素
        pq.pop();
        ans+=a+b;//合并消耗的能量值累加
        pq.push(a+b);//合并后再放入堆中
    }
    cout<<ans<<endl;//输出
    return 0;//完结撒花！
}