---
title: "合并果子"
created: 2025-11-28
tags:
  - 算法
---

# 合并果子

## 题目 [合并果子](https://www.acwing.com/problem/content/150/)

![[image-36e14ed4.png]]

## 思路分析

咋一看和前面的区间dp很像 但不一样的是 前面区间dp是只能选相邻的两堆进行合并

而这里 是可以选择任意两个进行合并的

那么 从贪心角度出发 每次选两个花费最小的进行合并呗

![[image-f68bd41c.png]]

发现 这不就是哈夫曼树的构造方法吗

emmm 这类贪心就是经典的 Huffman Tree 的二叉堆模型

每次取出两个最小值 合并成一个 又放进去供选择

这个数据结构很容易可以想到用小根堆

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

priority_queue<int,vector<int>,greater<int>> heap;

int n;

int main()

{

    cin>>n;

    while(n--){

        int x;cin>>x;

        heap.push(x);

    }

    int res=0;

    while(heap.size()>1){

        int min1=heap.top();

        heap.pop();

        int min2=heap.top();

        heap.pop();

        int cost=min1+min2;

        res+=cost;

        heap.push(cost);

    }

    cout<<res;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[k叉树 荷马史诗|k叉树 荷马史诗]] 🏠 [[00-刷题理模型]] ➡️ [[哈夫曼模型|哈夫曼模型]]