算法基础之合并果子

2024-01-09 17:31:10

合并果子

  • 核心思想: 贪心

    • Huffman树(算法):

      • 在这里插入图片描述

      • 每次将两个最小的堆合并 然后不断向上合并

    •   #include<iostream>
        #include<algorithm>
        #include<queue>  //用小根堆实现找最小堆
        
        using namespace std;
        int main()
        {
            int n;
            cin>>n;
            priority_queue<int ,vector<int> , greater<int>> heap;
            for(int i=0;i<n;i++)
            {
                int x;
                cin>>x;
                heap.push(x);
            }
            
            int res=0;
            while(heap.size()>1)
            {
                int a = heap.top();heap.pop();  //取出最小的两个堆
                int b = heap.top();heap.pop();
                res += a+b;
                heap.push(a+b);
            }
            
            cout<<res<<endl;
            return 0;
        }
      

文章来源:https://blog.csdn.net/Pisasama/article/details/135419174
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。