P1090 [NOIP2004 提高组] 合并果子

题目描述：P1090 [NOIP2004 提高组] 合并果子

---

解题思路

---

• 解题思路

  1、该题目与区间 DP的石子合并相似，但不同点在于该题可以选择任意两堆合并，而石子合并只能选择相邻两堆，且该题数据范围较大
  2、由于可以选择任意两堆，所以可以贪心。简单可知：合并的两堆果子，其中每一堆都重量越小越优，这样合并所需的力气更小，同时，两堆合并后的总重也更小，即下一次合并时这一堆果子贡献的重量更小。易证：每次都选择当前重量最小的两堆合并，可以得到所求最小值
  3、对于每次取出最小值的需求，可以使用优先队列维护，注意小根堆应使用 $\gt$ 作为比较运算符

---

代码实现

---

• 代码实现

  #include <bits/stdc++.h>
  using namespace std;
  
  void solve()
  {
      int n, ans = 0;
      cin >> n;
  
      priority_queue<int, vector<int>, greater<int>> pq; // 小根堆
      for (int i = 1; i <= n; i++)
      {
          int x;
          cin >> x;
          pq.push(x);
      }
  
      while (pq.size() > 1)
      {
          int x = pq.top();
          pq.pop();
          int y = pq.top();
          pq.pop();
          ans += x + y;
          pq.push(x + y);
      }
  
      cout << ans;
  }
  
  int main()
  {
      ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
      int T = 1;
      // cin >> T;
      while (T--)
          solve();
      return 0;
  }

---

页底评论

---