題目：農(nóng)夫約翰要修補(bǔ)圍墻，他有一塊很長(zhǎng)的木板，要把木板鋸成N塊木板，所鋸木板的長(zhǎng)度就是花費(fèi)，問如何花費(fèi)最小。比若8 8 5，總長(zhǎng)度是21，所以第一次鋸要花費(fèi)21，木塊據(jù)成8 13，然后13鋸成8 5，花費(fèi)13，總花費(fèi)為13+21=34.令一種鋸法是分成16 5，再分成8 8，但這樣的花費(fèi)是16+21=37。求花費(fèi)最小就是用huffman思想，用優(yōu)先隊(duì)列做。
#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;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
