【算法刷题分享】

算法刷题分享

（一）动态规划——背包专题
（二）贪心——区间专题
（三）回溯
（四）双指针问题
（五）分治
（六）贪心

（一）动态规划——背包专题

导语：动态规划是一种常用的算法思想，广泛应用于各类问题的求解中。而背包问题则是动态规划中最经典且常见的问题之一。背包问题涉及在给定容量的背包中选择物品以达到最优解的目标。本篇博客将专注于介绍和讨论与背包问题相关的动态规划算法。我们将探索不同类型的背包问题，并详细讲解其动态规划的解决思路。

题目：01背包问题 LeetCode 416

题目概述：01背包问题是最基础的背包问题之一。给定一组物品，每个物品有重量和价值，背包具有一定的容量，需要在不超过背包容量的前提下，选择物品使得总价值最大化。

题解：使用动态规划求解，定义dp[i][j]表示前i个物品放入容量为j的背包中所能达到的最大价值。状态转移方程如下：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])，其中w[i]表示第i个物品的重量，v[i]表示第i个物品的价值。

def knapsack01(weights, values, capacity):    n = len(weights)    dp = [[0] * (capacity + 1) for _ in range(n + 1)]     for i in range(1, n + 1):        for j in range(1, capacity + 1):            if weights[i - 1] <= j:                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])            else:                dp[i][j] = dp[i - 1][j]     return dp[n][capacity]

题目：完全背包问题 – LeetCode 322

题解：完全背包问题是一个经典的背包问题。给定一组面额不同的硬币和一个总金额，求出能够凑成总金额所需的最少硬币数量。使用动态规划求解，定义dp[i]表示凑成金额i所需的最少硬币数量。状态转移方程如下：dp[i] = min(dp[i], dp[i-coin] + 1)，其中coin表示硬币的面额。核心代码段：

def coinChange(coins, amount):    dp = [float('inf')] * (amount + 1)    dp[0] = 0     for coin in coins:        for i in range(coin, amount + 1):            dp[i] = min(dp[i], dp[i - coin] + 1)     return dp[amount] if dp[amount] != float('inf') else -1

题目：多重背包问题 – LeetCode 879

题解：多重背包问题是背包问题的一种扩展形式，每个物品有数量限制。给定一组工作，每个工作有所需的成本和利润，求出在不超过预算的前提下，能够获得的最大利润。使用动态规划求解，定义dp[i][j]表示前i个工作在预算不超过j的情况下所能达到的最大利润。状态转移方程如下：dp[i][j] = dp[i-1][j] + dp[i-1][j-cost]，其中cost表示第i个工作的成本。核心代码段：

def profitableSchemes(n, minProfit, group, profit):    m = len(group)    MOD = 10 ** 9 + 7    dp = [[0] * (minProfit + 1) for _ in range(n + 1)]    dp[0][0] = 1     for i in range(1, m + 1):        currGroup, currProfit = group[i - 1], profit[i - 1]        for j in range(n, currGroup - 1, -1):            for k in range(minProfit, -1, -1):                dp[j][k] += dp[j - currGroup][max(0, k - currProfit)]                dp[j][k] %= MOD     return sum(dp[n]) % MOD

题目：编辑距离 – LeetCode 72

核心思路：这是一个经典的编辑距离问题，可以使用动态规划来解决。我们定义一个二维数组 dp，其中 dp[i][j] 表示将字符串 A 的前 i 个字符转换为字符串 B 的前 j 个字符所需的最小操作数。通过状态转移方程更新 dp[i][j] 的值，最后返回数组的最后一个元素即可。

状态转移方程：dp[i][j] = dp[i-1][j-1] if A[i-1] == B[j-1] dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 otherwise

#include #include #include using namespace std;string s1, s2;int dp[50010][50010];int main(){  int l1, l2;  cin >> l1 >> s1 >> l2 >> s2;  for (int i = 0; i <= l1; ++i)  {    dp[i][0] = i;  }  for (int i = 0; i <= l2; ++i)  {    dp[0][i] = i;  }  for (int i = 1; i <= l1; ++i)  {    for (int j = 1; j <= l2; ++j)    {      if (s1[i] == s2[j])      {        dp[i][j] = dp[i - 1][j - 1];      }      else      {        dp[i][j] = min(dp[i - 1][j - 1] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j] + 1));      }    }  }  printf("%d", dp[l1][l2]);  return 0;}

时间复杂度分析：由于嵌套了两层循环，时间复杂度为 O(m * n)，其中 m 和 n 分别是字符串 A 和 B 的长度。

题目：石子合并 LeetCode 1000

核心思路：

这是一个经典的哈夫曼编码问题，也可以通过贪心算法来解决。我们可以使用一个优先队列（最小堆）来维护当前序列中的数，每次取出两个最小的数合并，并将合并后的数放回队列中，重复这个过程直到队列中只剩一个数。每次合并的代价是两个数的和，因此总的代价是所有合并的代价之和。

状态转移方程：

for(int len = 2; len <= n; len++) { 	for(int i = 1; i <= n-len+1; i++) { 		int j = i + len - 1; 		dp[i][j] = INT_MAX; 		for(int k = i; k < j; k++) { 			dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[i][j]); 		} 	}}

时间复杂度分析：

由于每次都是取出两个最小的数进行合并，然后再插入一个数，因此每次操作的时间复杂度为 O(log n)，总的时间复杂度为 O(n log n)，其中 n 是序列的长度。

题目：股票交易

核心思路：这是一个动态规划问题，可以通过状态机的方式进行建模。

时间复杂度分析：

由于只需遍历数组一次，时间复杂度为 O(n)，其中 n 是股票价格列表的长度。

#include#includeusing namespace std;const int N = 100010;int w[N],f[N][2];int n;int main(){  scanf("%d", &n);  for(int i=1;i<=n;i++) scanf("%d",&w[i]);   f[0][0]=0; f[0][1]=-1e6;  for(int i=1; i<=n; ++i){    f[i][0]=max(f[i-1][0],f[i-1][1]+w[i]);        f[i][1]=max(f[i-1][1],f[i-1][0]-w[i]);  }  cout<<f[n][0];}

（二）贪心——区间专题

导语：在算法问题中，区间类问题是一类常见而重要的问题。贪心算法是一种常用的解决区间类问题的方法，它通过每一步选择当前最优解来达到整体最优解的目标。本篇博客将介绍贪心算法在解决区间类问题中的应用，并提供几个示例来说明其实现过程。通过阅读本文，你将了解贪心算法的基本思想以及如何运用它解决不同类型的区间类问题。

题目：区间选点

题目描述：给定一组区间，从中选取尽可能多的互不相交的区间，使得选取的区间数最大。

题解：贪心法是解决区间选点问题的常用方法。首先，将所有区间按照右端点从小到大进行排序。然后，从第一个区间开始，选择右端点最小的区间，并排除与该区间相交的其他区间。重复该过程，直到遍历完所有区间。选取的区间即为答案。核心代码段：

void intervalSelection(vector<pair>& intervals) {    sort(intervals.begin(), intervals.end(), [](const pair& a, const pair& b) {        return a.second < b.second;    });     vector<pair> selectedIntervals;    int lastEnd = INT_MIN;     for (const auto& interval : intervals) {        if (interval.first > lastEnd) {            selectedIntervals.push_back(interval);            lastEnd = interval.second;        }    }     // 输出选取的区间    for (const auto& interval : selectedIntervals) {        cout << "[" << interval.first << ", " << interval.second << "]" << endl;    }}

题目：区间覆盖

题目描述：给定一组区间，找到最少的区间，使得它们的并集覆盖整个区间范围。

题解：贪心法是解决区间覆盖问题的常用方法。首先，将所有区间按照右端点从小到大进行排序。然后，从第一个区间开始，选择最小的右端点，并排除与该右端点相交的其他区间。重复该过程，直到覆盖整个区间范围。核心代码段：

void intervalCover(vector<pair>& intervals) {    sort(intervals.begin(), intervals.end(), [](const pair& a, const pair& b) {        return a.second < b.second;    });     vector<pair> selectedIntervals;    int lastEnd = INT_MIN;    int minRight = INT_MAX;     for (const auto& interval : intervals) {        if (interval.first > lastEnd) {            selectedIntervals.push_back(interval);            lastEnd = interval.second;            minRight = min(minRight, interval.second);        }    }     // 输出选取的区间    for (const auto& interval : selectedIntervals) {        cout << "[" << interval.first << ", " << interval.second << "]" << endl;    }}

题目：区间分组

题目描述：给定一组区间，将它们划分为尽可能少的组，使得每组中的区间互不相交。

题解：贪心法是解决区间分组问题的常用方法。首先，将所有区间按照右端点从小到大进行排序。然后，遍历每个区间，将它与当前组中的最后一个区间进行比较。如果不相交，则将该区间加入当前组；如果相交，则新建一组，并将该区间加入新的组。重复该过程，直到遍历完所有区间。核心代码段：

void intervalGroup(vector<pair>& intervals) {    sort(intervals.begin(), intervals.end(), [](const pair& a, const pair& b) {        return a.second < b.second;    });     vector<vector<pair>> groups;    groups.push_back({intervals[0]});     for (int i = 1; i < intervals.size(); ++i) {        bool placed = false;        for (auto& group : groups) {            if (group.back().second < intervals[i].first) {                group.push_back(intervals[i]);                placed = true;                break;            }        }        if (!placed) {            groups.push_back({intervals[i]});        }    }     // 输出分组结果    for (int i = 0; i < groups.size(); ++i) {        cout << "Group " << i + 1 << ":" << endl;        for (const auto& interval : groups[i]) {            cout << "[" << interval.first << ", " << interval.second << "]" << endl;        }        cout << endl;    }}

（三）回溯

导语：回溯法是一种经典的算法思想，通常用于解决组合、排列、子集等问题。它通过尝试所有可能的选择来递归地搜索解空间，直到找到满足条件的解或遍历完所有可能的选择。本部分博客将汇总一些常见的使用回溯法解决的算法题，并给出它们的简要题解和核心代码段。

题目：全排列 – LeetCode 46

题目描述：给定一个没有重复数字的序列，返回其所有可能的全排列。

题解：使用回溯法递归地生成所有可能的排列。从第一个位置开始，依次将每个数字放置在当前位置，然后继续递归处理下一个位置，直到所有位置都被填满。需要注意的是，在回溯之前要将当前位置的数字恢复原样。核心代码段：

void backtrack(vector& nums, vector<vector>& res, int start) {    if (start == nums.size()) {        res.push_back(nums);        return;    }    for (int i = start; i < nums.size(); i++) {        swap(nums[start], nums[i]);        backtrack(nums, res, start + 1);        swap(nums[start], nums[i]);    }} vector<vector> permute(vector& nums) {    vector<vector> res;    backtrack(nums, res, 0);    return res;}

题目：组合总和 – LeetCode 39

题目描述：给定一个无重复元素的正整数数组 candidates 和一个目标整数 target，找出 candidates 中所有可以使数字和为 target 的组合。

题解：使用回溯法递归地生成所有可能的组合，并根据条件进行剪枝。从第一个位置开始，依次将每个数字放置在当前位置，然后继续递归处理下一个位置，直到满足条件或超出目标值。需要注意的是，在回溯之前要将当前位置的数字恢复原样。核心代码段：

void backtrack(vector& candidates, vector<vector>& res, vector& combination, int target, int start) {    if (target == 0) {        res.push_back(combination);        return;    }    for (int i = start; i < candidates.size(); i++) {        if (candidates[i] > target) {            break;        }        combination.push_back(candidates[i]);        backtrack(candidates, res, combination, target - candidates[i], i);        combination.pop_back();    }} vector<vector> combinationSum(vector& candidates, int target) {    vector<vector> res;    vector combination;    backtrack(candidates, res, combination, target, 0);    return res;}

题目：子集 – LeetCode 78

题目描述：给定一个不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

题解：使用回溯法递归地生成所有可能的子集。从第一个位置开始，依次选择包含当前元素和不包含当前元素两种情况，然后继续递归处理下一个位置。需要注意的是，在回溯之前要将当前元素加入或移除子集中。核心代码段：

void backtrack(vector& nums, vector<vector>& res, vector& subset, int start) {    res.push_back(subset);    for (int i = start; i < nums.size(); i++) {        subset.push_back(nums[i]);        backtrack(nums, res, subset, i + 1);        subset.pop_back();    }} vector<vector> subsets(vector& nums) {    vector<vector> res;    vector subset;    backtrack(nums, res, subset, 0);    return res;}

（四）双指针问题

导语：双指针法是一种常用的算法思想，通过两个指针在数组或链表等数据结构上的移动，来解决一些特定的问题。本部分博客将汇总一些常见的算法题，并给出它们的双指针法解决方案。希望这些例题能够帮助你理解和掌握双指针法的应用。

题目：两数之和 – LeetCode 1

题目描述：给定一个升序排列的整数数组和一个目标值，找出数组中和为目标值的两个数的下标。

题解：使用两个指针分别指向数组的首尾元素，根据两个指针指向的元素之和与目标值的关系，逐步调整指针的位置，直到找到目标值或遍历完整个数组。核心代码段：

// 两数之和问题vector twoSum(vector& nums, int target) {    int left = 0, right = nums.size() - 1;    while (left < right) {        int sum = nums[left] + nums[right];        if (sum == target) {            // 找到目标值，返回结果            return {left, right};        } else if (sum < target) {            left++;        } else {            right--;        }    }    // 没有找到目标值，返回默认结果    return {-1, -1};}

题目：反转字符串- LeetCode 344

题目描述：给定一个字符串，将其原地反转。

题解：使用两个指针分别指向字符串的首尾字符，交换两个指针所指向的字符，并逐步向中间移动指针，直到两个指针相遇。核心代码段：

// 反转字符串问题void reverseString(string& s) {    int left = 0, right = s.length() - 1;    while (left < right) {        swap(s[left], s[right]);        left++;        right--;    }}

题目：删除排序数组中的重复项- LeetCode 26

题目描述：给定一个有序数组，删除数组中重复的元素，使每个元素只出现一次，并返回新数组的长度。

题解：使用两个指针，一个指针用于遍历数组，另一个指针用于记录非重复元素的位置，当遍历到不重复的元素时，将其复制到非重复元素的位置，并更新非重复元素指针的位置。核心代码段：

// 删除排序数组中的重复项问题int removeDuplicates(vector& nums) {    int i = 0, j = 1;    while (j < nums.size()) {        if (nums[j] != nums[i]) {            i++;            nums[i] = nums[j];        }        j++;    }    return i + 1;}

题目：盛最多水的容器- LeetCode 11

题目描述：给定一个非负整数数组，每个元素表示一个竖直线的高度，找出两条线与 x 轴共同构成的容器可以容纳的最大水量。

题解：使用两个指针分别指向数组的首尾元素，计算当前指针构成的容器的面积，并记录最大面积，然后根据两个指针所指向的元素的高度来决定移动哪个指针。核心代码段：

// 盛最多水的容器问题int maxArea(vector& height) {    int left = 0, right = height.size() - 1;    int maxArea = 0;    while (left < right) {        int area = min(height[left], height[right]) * (right - left);        maxArea = max(maxArea, area);        if (height[left] < height[right]) {            left++;        } else {            right--;        }    }    return maxArea;}

（五）分治

逆序对的数量

核心思路：

这是一个典型的分治问题。我们可以使用归并排序的思想，在归并的过程中计算逆序对的数量。具体步骤如下：将数组分成两半，并递归地计算每个子数组的逆序对数量。在归并的过程中，合并两个有序的子数组，同时统计跨越两个子数组的逆序对数量。

最后将结果返回。

时间复杂度：归并排序的时间复杂度是 O(n log n)，其中 n 是数组的长度。

#include using namespace std;const int N = 100010;int n;int a[N], tmp[N];long long merge_sort(int l, int r){    if( l >= r) return 0;    long long ans = 0;    int mid = (l + r) >> 1;    ans = merge_sort(l, mid) + merge_sort(mid+1, r);    int k=0, i=l, j=mid+1;    while(i <= mid && j <= r){        if(a[i] <= a[j]) tmp[k++] = a[i++];        else{            tmp[k++] = a[j++];            ans += mid - i + 1; //第一个里面的i后面的所有         }    }    while(i <= mid) tmp[k++] = a[i++];    while(j <= r) tmp[k++] = a[j++];    for(int i=l,k=0; i <= r; i++, k++) a[i] = tmp[k];    return ans;}int main(){    cin >> n;    for(int i = 0; i > a[i];    cout << merge_sort(0, n-1) << endl;    return 0;}

最大连续子数组和

核心思路：

这道题可以通过分治的策略来解决。分治的思想是将问题划分为更小的子问题，解决子问题，然后合并子问题的解。

在这里，我们将数组分为左右两部分，分别找出左半部分和右半部分的最大子数组和，然后再考虑跨越左右两部分的最大子数组和。最终的结果是这三个值中的最大值。
具体的步骤如下：

将数组分为左右两半，分别递归求解左半部分和右半部分的最大子数组和。

对于跨越左右两部分的最大子数组，分别找出包含左半部分最右边元素的最大子数组和包含右半部分最左边元素的最大子数组。两者相加得到跨越两部分的最大子数组和。

返回左半部分最大子数组和、右半部分最大子数组和、跨越两部分的最大子数组和中的最大值。
时间复杂度：

分治算法的时间复杂度通常为 O(n log n)，其中 n 是数组的长度。

#include 
#include 
#include 
#define LL long long int
using namespace std;
vector nums;
int dp[10020];
int main()
{
  int len;
  scanf("%d", &len);
  for (int i = 0; i < len; ++i)
  {
    int t;
    scanf("%d", &t);
    nums.push_back(t);
  }
  // dp[i] 表示：以 nums[i] 结尾的连续子数组的最大和
  dp[0] = nums[0];
  for (int i = 1; i < len; i++)
  {
    if (dp[i - 1] > 0)
    {
      dp[i] = dp[i - 1] + nums[i];
    }
    else
    {
      dp[i] = nums[i];
    }
  }

  // 也可以在上面遍历的同时求出 res 的最大值，这里我们为了语义清晰分开写，大家可以自行选择
  int res = dp[0];
  for (int i = 1; i < len; i++)
  {
    res = max(res, dp[i]);
  }
  printf("%d", res);
  return 0;
}

砍树

核心思路：

这个问题可以通过分治的策略来解决。分治的思想是将问题划分为更小的子问题，解决子问题，然后合并子问题的解。
具体的步骤如下：

首先，找到所有树的高度的中位数（Median）。

对于所有树的高度，将高度大于中位数的部分作为一个子问题，递归求解这个子问题。

在递归的过程中，通过二分查找找到一个合适的木材长度，使得大于等于这个长度的木材段数达到或接近 k。

返回递归结果。

这个方法的核心在于通过找到中位数，将问题划分为两个子问题，然后通过递归和二分查找来找到合适的木材长度。
时间复杂度：

分治算法的时间复杂度通常为 O(n log n)，其中 n 是树的数量。

#include #include #include #include #include #include #include #include #define LL long long intusing namespace std;const int N = 10000020;int a[N];int check(int n, int l){  int sum = 0;  for_each(a, a + n, [&l, &sum](int e)           { sum += e / l; });  return sum;}int main(int argc, char **argv){  ios::sync_with_stdio(false);  int n, k;  cin >> n >> k;  for (int i = 0; i > a[i];  int i = 0, j = 0;  for_each(a, a + n, [&j](int e)           { j = max(j, e); });  while (i < j)  {    int mid = (i + j + 1) >> 1;    if (check(n, mid) < k)    {      j = mid - 1;    }    else    {      i = mid;    }  }  cout << i << endl;  return 0;}

数列分段

可以使用分治的思想来解决。分治的基本思想是将原问题划分为更小的子问题，分别解决子问题，最后合并子问题的解。

在这个问题中，我们可以使用二分查找来确定每一段的和的最大值。具体步骤如下：

确定二分查找的左右边界，左边界为数组中的最大值，右边界为数组的和。

在每一次二分查找中，计算中间值 mid，并判断是否能够将数组分成 M 段，使得每段的和不超过 mid。

如果可以，则说明 mid 过大，继续在左半部分查找；如果不行，则说明 mid 过小，继续在右半部分查找。

最终返回二分查找的结果。

时间复杂度：

由于二分查找的时间复杂度是 O(log(sum(nums) – max(nums)))，其中 sum(nums) 是数组的和，max(nums) 是数组中的最大值，因此总的时间复杂度是 O(log(sum(nums) – max(nums)))。

（六）贪心

采购礼物

核心思路：

这是一个典型的贪心算法问题。贪心算法的基本思想是每次都选择当前情况下的最优解，

期望通过局部最优解达到全局最优解。

在这个问题中，我们可以按照礼物的价格从低到高排序，然后依次购买，直到小红的钱不够为止。

步骤：

对所有礼物按价格进行排序。

从最便宜的礼物开始，逐个购买，直到小红的钱不够为止。

时间复杂度：

由于排序的时间复杂度为 O(n log n)，其中 n 是礼物的数量，贪心算法的购买过程的时间复杂度是 O(n)，因此总的时间复杂度为 O(n log n)。
部分背包

核心思路：

这是一个经典的贪心算法问题，通常被称为分数背包问题。贪心算法的基本思想是每次都选择当前情况下的最优解，期望通过局部最优解达到全局最优解。

在这个问题中，我们可以按照金币的单位价值（价值/重量）从高到低进行排序，然后依次选择单位价值最高的金币放入背包。

步骤：

计算每堆金币的单位价值。

按照单位价值从高到低对金币进行排序。

依次选择单位价值最高的金币放入背包，直到背包装满或没有更多金币。

时间复杂度：

由于排序的时间复杂度为 O(n log n)，其中 n 是金币的数量，贪心算法的选择过程的时间复杂度是 O(n)，因此总的时间复杂度为 O(n log n)。
区间选点

核心思路：

这是一个典型的贪心算法问题，通常被称为区间调度问题。贪心算法的基本思想是每次都选择当前情况下的最优解，期望通过局部最优解达到全局最优解。

在这个问题中，我们可以按照区间的结束点从小到大进行排序，然后依次选择结束点最小的区间，将点放在该区间的结束点上。这样，可以保证每个区间至少包含一个选出的点。

步骤：

对所有区间按照结束点从小到大进行排序。

从第一个区间开始，选择结束点作为一个选出的点，并移动到下一个未覆盖的区间的起始点。

重复步骤 2，直到所有区间都被覆盖。

时间复杂度：

由于排序的时间复杂度为 O(N log N)，其中 N 是区间的数量，贪心算法的选择过程的时间复杂度是 O(N)，因此总的时间复杂度为 O(N log N)。
数列分段

核心思路：

这是一个典型的贪心算法问题，通常被称为分割数列问题。贪心算法的基本思想是每次都选择当前情况下的最优解，期望通过局部最优解达到全局最优解。

在这个问题中，我们可以按照顺序遍历数列，尽量将数列划分成若干连续的子段，使得每个子段的元素和不超过 M。具体步骤如下：

从头到尾遍历数列，累加元素，直到累加和超过 M。

当累加和超过 M 时，表示当前子段结束，记录这个子段的长度，并重新开始累加。

重复步骤 1 和步骤 2，直到遍历完整个数列。

时间复杂度：

由于只需遍历一次数列，时间复杂度为 O(N)，其中 N 是数列的长度。
仓库选址

核心思路：

这是一个经典的问题，通常被称为最佳位置选择问题。解决这个问题的关键是找到一个位置，使得到所有商店的距离之和最小。这个位置就是货仓的最佳位置。

一种有效的方法是通过排序坐标数组，找到中位数对应的坐标作为货仓的位置。这是因为对于任何一个点，到其他点的距离之和最小的点就是中位数。因此，通过选择中位数的位置，可以使得总距离最小。

步骤：

对坐标数组进行排序。

选择排序后的坐标数组的中位数作为货仓的位置。

时间复杂度：

由于只需对坐标数组进行一次排序，时间复杂度为 O(N log N)，其中 N 是商店的数量。
均分图书

这个问题其实是一个典型的贪心算法问题。为了达到最快的平衡，每一步都应尽量使当前堆与平均数接近。从第一堆开始，我们看它与平均值的差异，并将这个差值的图书移到第二堆，以此类推，直到最后一堆。每移动一次，都记录移动的次数，最后输出总的移动次数。

时间复杂度为 O（n）
合并果子

这个问题是一个典型的贪心算法问题，也被称作“合并果子”或“最小堆”。基本思路是每次合并最轻的两堆果子，这样可以保证总的合并代价最小。可以采用最小堆来找到最小的果子堆。