3014 - 【设计型】第11章：指针和数组 Huffuman树（1）

Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。
　　给出一列数{pi}={p0, p1, …, pn-1}，用这列数构造Huffman树的过程如下：
　　1. 找到{pi}中最小的两个数，设为pa和pb，将pa和pb从{pi}中删除掉，然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb。
　　2. 重复步骤1，直到{pi}中只剩下一个数。
　　在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。
　　本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。

　　例如，对于数列{pi}={5, 3, 8, 2, 9}，Huffman树的构造过程如下：
　　1. 找到{5, 3, 8, 2, 9}中最小的两个数，分别是2和3，从{pi}中删除它们并将和5加入，得到{5, 8, 9, 5}，费用为5。
　　2. 找到{5, 8, 9, 5}中最小的两个数，分别是5和5，从{pi}中删除它们并将和10加入，得到{8, 9, 10}，费用为10。
　　3. 找到{8, 9, 10}中最小的两个数，分别是8和9，从{pi}中删除它们并将和17加入，得到{10, 17}，费用为17。
　　4. 找到{10, 17}中最小的两个数，分别是10和17，从{pi}中删除它们并将和27加入，得到{27}，费用为27。

<span style="font-family:宋体, 'Times New Roman';font-size:14px;line-height:22px;background-color:#E4F1FF;">　　5. 现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。</span>

<span><span style="font-size:14px;line-height:22px;background-color:#E4F1FF;"><strong>注：该过程每次只删去两个数，如同时有5,5,5那么只删去两个5，三个元素变成两个元素5,10</strong></span></span>

Input

输入的第一行包含一个正整数n。
接下来是n个正整数，表示p0, p1, …, pn-1，每个数不超过1000。

Output

输出用这些数构造Huffman树的总费用。

Examples

Input

5
5 3 8 2 9

Output

Solution C

#include <stdio.h>
#include <stdlib.h>

int *input(int n)
{
	int *T, *p;
	int i = 0, j = 0, temp, pos;
	T = (int*) malloc(sizeof (int) * (n));
    for (i = 0; i < n; i++)
    {
		p = T;
        scanf("%d", &temp);
		for (j = 0; j < i; j++)
		{
			if(*p < temp)
				break;
			p++;
		}
		pos = j;
		for (j = i; j > pos; j--)
		{
			*(T + j) = *(T + j - 1);
		}
		*(T + j) = temp;
    }
	return T;
}
int huffman(int *T, int n)
{
	int *p;
	int j = 0, pos, cost;
	cost = *(T + n - 1) + *(T + n - 2);
	p = T;
	for (j = 0; j < n - 2; j++)
	{
		if(*p < cost)
			break;
		p++;
	}
	pos = j;
	for (j = n - 2; j > pos; j--)
	{
		*(T + j) = *(T + j - 1);
	}
	*(T + j) = cost;
	return cost;
}
int main(void)
{
    int i = 0, n = 0, l = 0, cost = 0;
	int *T;
	scanf("%d", &n);
    T = input(n);
	for (l = n; l > 1; l--)
    {
		cost += huffman(T, l);
    }
	printf("%d\n", cost);
    return 0;
}

Solution C++

#include<iostream>
using namespace std;

int sum = 0;

int main()
{
	int N;
	cin >> N;
	int *num = new int[N];
	for(int i = 0; i < N; i++)
	{
		cin >> num[i];
	}
	int min = 0;
	int min_d = 0;
	int min_mid = 0;
	int min_dmid = 0;
	for(int count = N; count > 1; count--)
	{
		min_mid = 0;
		min_dmid = 0;
		for(int i = 0; i < N; i++)
		{
			if((num[i] != 0) && (num[i] < num[min]))
			{
				min = i;
			} 
		}
		//令mid_d为不等于min的一个值，排除num[min]后求剩下的元素最小值 
		for(int i = 0; i < N; i++)
		{
			if((num[i] != 0) && (i != min)) 
			{
				min_d = i;
				break; 
			}
		}
		for(int i = 0; i < N; i++)
		{
			if(i == min) continue;
			else
			{
				if((num[i] != 0) && (num[i] < num[min_d]))
				{
					min_d = i;
				}
			}
		} 
		min_dmid = num[min_d];//因为相加后就得将改坐标删除，所以用两个中间变量记录两个最小值 
		min_mid = num[min];
	    num[min_d] = 0;
		num[min] = min_mid + min_dmid;
		sum += num[min];
	}
	cout << sum << endl;
	delete [] num;
	return 0;
}

Time Limit	1 second
Memory Limit	128 MB

Discuss Stats

上一题下一题