前言 這道題耗時將近半個月，期間我復習了幾處基礎知識 貪心算法 堆排序 哈夫曼樹 最後在參考我同學的博客，終於通過最小堆構建最小優先級隊列ac了這道題！ 推薦一下我同學的博客，內容很好而且人也很犀利 ： http://blog.csdn.net/cscmaker/article/details/8138870 題目 [html] view plaincopy 題目描述： 在一個果園裡，小明已經將所有的水果打了下來，並按水果的不同種類分成了若干堆，小明決定把所有的水果合成一堆。每一次合並，小明可以把兩堆水果合並到一起，消耗的體力等於兩堆水果的重量之和。當然經過 n‐1 次合並之後，就變成一堆了。小明在合並水果時總共消耗的體力等於每次合並所耗體力之和。 假定每個水果重量都為 1，並且已知水果的種類數和每種水果的數目，你的任務是設計出合並的次序方案，使小明耗費的體力最少，並輸出這個最小的體力耗費值。例如有 3 種水果，數目依次為 1，2，9。可以先將 1，2 堆合並，新堆數目為3，耗費體力為 3。然後將新堆與原先的第三堆合並得到新的堆，耗費體力為 12。所以小明總共耗費體力=3+12=15，可以證明 15 為最小的體力耗費值。 輸入： 每組數據輸入包括兩行,第一行是一個整數 n(1<=n<=10000),表示水果的種類數，如果 n 等於 0 表示輸入結束，且不用處理。第二行包含 n 個整數，用空格分隔，第 i 個整數(1<=ai<=1000)是第 i 種水果的數目。 輸出： 對於每組輸入，輸出一個整數並換行，這個值也就是最小的體力耗費值。輸入數據保證這個值小於 2^31。 樣例輸入： 3 9 1 2 0 樣例輸出： 15 ac代碼 [cpp] #include <stdio.h> #include <stdlib.h> #define NUM 10001 void minHeapIfy(int *A, int i, int n); void buildMinHeap(int *A, int n); int heapExtractMin(int *A, int n); void heapIncreaseKey(int *A, int i, int key); int moveFruit(int *A, int n); int main() { int i , n, power, weight[NUM]; while(scanf("%d", &n) != EOF && n != 0) { //接收客戶端參數 for(i = 1; i <= n; i ++) { scanf("%d", &weight[i]); } //貪心選擇 power = moveFruit(weight, n); printf("%d\n", power); } return 0; } /** * Description:維護以ｉ為根節點的最小堆 */ void minHeapIfy(int *A, int i, int n) { int min, loc, r, l, change; for(min = i; min <= n;) { l = min * 2; r = min * 2 + 1; loc = min; if(l <= n && A[l] < A[min]) min = l; if(r <= n && A[r] < A[min]) min = r; if(loc != min) { change = A[min]; A[min] = A[loc]; A[loc] = change; }else { break; } } } /** * Description:去掉並返回堆中最小的元素 */ int heapExtractMin(int *A, int n) { int max = A[1]; A[1] = A[n]; minHeapIfy(A, 1, n - 1); return max; } /** * Description:建立最小堆 */ void buildMinHeap(int *A, int n) { int i; for(i = n / 2; i >= 1; i --) { minHeapIfy(A, i, n); } } /** * Description:將元素插入到最小優先隊列 */ void heapIncreaseKey(int *A, int i, int key) { int parent, change; for(A[i] = key, parent = i / 2; i >= 1 && A[parent] > A[i] && parent >= 1;) { change = A[parent]; A[parent] = A[i]; A[i] = change; i = parent; parent = i / 2; } } int moveFruit(int *A, int n) { int power, i, lchild, rchild, parent, j; buildMinHeap(A, n); for(i = 1, j = n, power = 0; i < n; i ++) { lchild = heapExtractMin(A, j); j -= 1; rchild = heapExtractMin(A, j); parent = lchild + rchild; power += lchild + rchild; heapIncreaseKey(A, j, parent); } return power; }
