算法基础之合并果子

合并果子

• 核心思想： 贪心

  • 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;}