首页 > ACM题库 > HDU-杭电 > hdu 2527 Safe Or Unsafe-优先队列-[解题报告]C++
2014
02-09

hdu 2527 Safe Or Unsafe-优先队列-[解题报告]C++

Safe Or Unsafe

问题描述 :

Javac++ 一天在看计算机的书籍的时候,看到了一个有趣的东西!每一串字符都可以被编码成一些数字来储存信息,但是不同的编码方式得到的储存空间是不一样的!并且当储存空间大于一定的值的时候是不安全的!所以Javac++ 就想是否有一种方式是可以得到字符编码最小的空间值!显然这是可以的,因为书上有这一块内容–哈夫曼编码(Huffman Coding);一个字母的权值等于该字母在字符串中出现的频率。所以Javac++ 想让你帮忙,给你安全数值和一串字符串,并让你判断这个字符串是否是安全的?

输入:

输入有多组case,首先是一个数字n表示有n组数据,然后每一组数据是有一个数值m(integer),和一串字符串没有空格只有包含小写字母组成!

输出:

输入有多组case,首先是一个数字n表示有n组数据,然后每一组数据是有一个数值m(integer),和一串字符串没有空格只有包含小写字母组成!

样例输入:

2
12
helloworld
66
ithinkyoucandoit

样例输出:

no
yes

题目描述

        HDU 2527

分析

        霍夫曼编码的应用。
        本题没有必要构造一棵完整的霍夫曼树。只需利用霍夫曼编码的原理,每次挑选频率最低的两个元素进行合并。(显然,可以利用优先级队列,这里用数组来模拟)

源码

//每次挑出现频率最小的两个元素,应该用优先级队列!!!!!!!!!!

#include <stdio.h>
#include <limits.h>
#include <string.h>
int unionFre(int fre[26]);

int main()
{
	int frequency[26];    //记录每个字母出现的频率
	int n;
	int m;
	char input[10000];
	int letterNum;     //出现的小写字母的个数
	int len;
	int result;
	int i, j;

	scanf("%d", &n);
	while (n --)
	{
		scanf("%d", &m);
		scanf("%s", &input);
		//初始化
		memset(frequency, 0, sizeof(frequency));

		//统计每个字母出现的次数
		len = strlen(input);
		for (i = 0; i < len; i ++)
		{
			frequency[input[i]-'a'] ++;
		}
		//没出现的字母频率均设为最大值
		letterNum = 26;
		for (i = 0; i < 26; i ++)
		{
			if (frequency[i] == 0)
			{
				letterNum --;
				frequency[i] = INT_MAX;
			}
		}

		//如果字符串只由一个字母组成
		if (letterNum == 1)
		{
			result = frequency[input[0]-97];
			if (result <= m)
				printf("yes\n");
			else
				printf("no\n");

			continue;
		}

		//循环(letterNum-1)次,每次挑选出现频率最低的两个元素进行合并
		//并更新result值,加上被合并的两个元素的频率和
		result = 0;
		for (i = 0; i < letterNum-1; i ++)
		{
			result = result + unionFre(frequency);
		}

		if (result <= m)
			printf("yes\n");
		else
			printf("no\n");
	}

	return 0;
}

//合并函数
int unionFre(int fre[26])
{
	int min, secondMin;
	int minIndex, secondMinIndex;
	int temp;
	int i;

	min = fre[0];
	minIndex = 0;
	secondMin = fre[1];
	secondMinIndex = 1;

	if (min > secondMin)
	{
		temp = min;
		min = secondMin;
		secondMin = temp;

		temp = minIndex;
		minIndex = secondMinIndex;
		secondMinIndex = temp;
	}

	//找出频率最低的两个元素
	for (i = 2; i < 26; i ++)
	{
		if (fre[i] < min)
		{
			secondMin = min;
			secondMinIndex = minIndex;

			min = fre[i];
			minIndex = i;
		}
		else if (fre[i] < secondMin)
		{
			secondMin = fre[i];
			secondMinIndex = i;
		}
	}

	//合并两个元素
	fre[minIndex] = min + secondMin;
	fre[secondMinIndex] = INT_MAX;

	return (min + secondMin);
}

解题转自:http://blog.csdn.net/cgz372619/article/details/10232009


  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  2. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?