アルゴリズムノート練習9.7問題C:果物をマージ(スタック)

アルゴリズムノート練習問題解合集
本題リンク
タイトル
テーマは1つの果樹園で説明して、多くはすでにすべての果物を打って、しかも果物の異なる種類によって異なる山に分けました.すべての果物をたくさん合成することにした.合併するたびに、多くの場合、2つの果物を統合することができ、消費された体力は2つの果物の重量の和に等しい.すべての果物はn-1回の合併を経て、1山しか残っていないことがわかる.果物を合併するときに消費される体力の多くは、合併するたびに消費される体力の和に等しい.これらの果物を家に運ぶのに力を入れなければならないので、果物を合併するときはできるだけ体力を節約しなければならないことが多い.各果物の重量が1であり、既知の果物の種類数と各果物の数を仮定すると、あなたの任務は合併の順序案を設計し、多くの体力を最小限に抑え、この最小の体力消費値を出力することです.例えば3種類の果物があり、数は1,2,9の順である.まず1、2スタックを統合することができ、新しいスタックの数は3で、体力を消費するのは3です.次に、新しいスタックを元の第3のスタックと統合し、新しいスタックを得、数は12であり、体力は12である.そのため、体力=3+12=15を多く消費します.15が最小の体力消費値であることが証明される.
入力ファイルfruitを入力.inは2行を含み、第1行は整数n(1<=n<=30000)であり、果物の種類数を表す.2行目はn個の整数を含み、スペースで区切られ、i番目の整数ai(1<=ai<=20000)はi番目の果物の数である.
出力ファイルfruit.outには1つの整数、すなわち最小の体力消費値しか含まれていない行が含まれます.入力データは、この値が231未満であることを保証する.
サンプル入力

10
3 5 1 7 6 4 2 5 4 1

サンプル出力

120

構想
直感的に見ると、毎回最小の2つの数字を取り出して加算し、1つのデータだけが答えになるまで戻します.
すべての入力データを使用して、ans = 0となるように小さなトップスタックを構築し、スタックのサイズheapSizeが1より大きい場合、次のサイクルを行います.

はtempでスタックトップの数を暫定的に記す.

は、スタックトップheap[1]とスタックテールheap[heapSize]の数を交換し、heapSizeを1減少させる.

スタックがスタックの性質に合致するように調整する.

は、スタックheap[1]にtempを加えたものである.

はansにheap[1]を加えたものである.

スタックがスタックの性質に合致するように調整する.

コード#コード#

#include 
#include 
#define MAX 30010

int heap[MAX];

void downAdjust(int low, int high) {
	int i = low, j = i * 2;
	while (j <= high) {
		if (j + 1 <= high && heap[j + 1] < heap[j])
			++j;
		if (heap[j] < heap[i]) {
			std::swap(heap[j], heap[i]);
			i = j;
			j = 2 * i;
		} else
			break;
	} 
} 
void createHeap(int n) {
	for (int i = n / 2; i >= 1; --i)
		downAdjust(i, n);
}

int main() {
	int n, tempN, sum;
	while (scanf("%d", &n) != EOF) {
		sum = 0;
		for (int i = 1; i <= n; ++i)
			scanf("%d", &heap[i]);
		createHeap(n);
		tempN = n;
		for (int i = 1; i <= n - 1; ++i) {
			int temp = heap[1];
			heap[1] = heap[tempN--];
			downAdjust(1, tempN); 
			heap[1] += temp;
			sum += heap[1];
			downAdjust(1, tempN);
		}
		printf("%d
", sum);
	} 
	return 0;
}