題目：農夫約翰要修補圍墻，他有一塊很長的木板，要把木板鋸成N塊木板，所鋸木板的長度就是花費，問如何花費最小。比若8 8 5，總長度是21，所以第一次鋸要花費21，木塊據成8 13，然后13鋸成8 5，花費13，總花費為13+21=34.令一種鋸法是分成16 5，再分成8 8，但這樣的花費是16+21=37。求花費最小就是用huffman思想，用優先隊列做。
#include <queue>#include <iostream>using namespace std;int main(){ int n,num; long long res = 0; int a,b; cin >> n; PRiority_queue<int,vector<int>,greater<int> > que; for(int i = 0; i < n; ++i) { cin >> num; que.push(num); } while(que.size() != 1) { a = que.top(); que.pop(); b = que.top(); que.pop(); res += (a+b); que.push(a+b); } cout << res << endl; return 0;}新聞熱點
疑難解答
