Hduoj2527[하프만 나무]

/*Safe Or Unsafe 
Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 9   Accepted Submission(s) : 5
Problem Description
Javac++              ，          ！                     ，            
         ！                     ！  Javac++                         ！
       ，          --     (Huffman Coding)；                      。  Javac++ 
     ，            ，                ？
 
Input
     case，       n   n   ，             m(integer)，                    ！
 
Output
                    yes，    no。
 
Sample Input
2
12
helloworld
66
ithinkyoucandoit
 
Sample Output
no
yes

Source
HDU 2008-10 Programming Contest
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char s[10000010];
int mark[27], n, m;
int cmp(const void *a, const void*b)
{
	return *(int *)a - *(int *)b;
}
void sort(int x)
{
	int i, j, k;
	k = mark[x];
	for(i = x+1; i < 26; ++i)
	{
		if(mark[i] >= k)
		{
			for(j = x; j < i; ++j)
			mark[j] = mark[j+1];
			mark[i] = k;
			return ;
		}
	}
	for(j = x; j < 25; ++j)
	mark[j] = mark[j+1];
	mark[25] = k;
}
int main()
{
	int i, j, k, t, ans;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d", &n);
		getchar();
		gets(s);
		m = strlen(s);
		memset(mark, 0, sizeof(mark));
		ans = 0;
		for(i = 0; i < m; ++i)
		mark[s[i] - 'a']++;
		qsort(mark, 26, sizeof(mark[0]), cmp);
		for(i = 0; i < 26; ++i)
		{
			if(mark[i] != 0)
			{
				for(j = i; j < 26; ++j)
				{
					mark[j+1] += mark[j];
					ans += mark[j+1];
					sort(j+1);
				}
				if(ans != mark[26])//              
				ans -= mark[26];
				break;
			}
		}
		if(ans <= n)
		printf("yes
");
		else
		printf("no
");
	}
	return 0;
}

제목: 문자열을 보여 줍니다. 문자열의 모든 알파벳은 하나의 값을 가지고 있습니다. 그 값은 문자열에 나타나는 주파수입니다. 현재 모든 알파벳의 값을 하나의 노드로 하프만 트리의 구조를 요구하고 트리의 값이 안전값보다 작은지 여부를 계산합니다. yes를 출력하면 no입니다.
사고방식: 이 문제는 하프만 나무에 대한 이해를 고찰한 것이다. 처음에 하프만 나무의 권한을 어떻게 계산했는지 잊어버렸다...계속 틀리기 때문에 하프만 나무에 대한 정의를 분명히 해야 한다. 나무의 권한은 비잎 노드의 총체이다. 그래서 나는 욕심을 내서 한다. 즉, 먼저 소유권 값을 오름차순으로 정렬하고 매번 수조에서 2개의 가장 작은 값을 꺼내서 더하면 추가된 이 수는 틀림없이 비잎 노드가ans에 들어간 것이다.그 다음에 덧셈을 한 후에 수조 중의 앞수를 직접 버리고 새로 덧셈한 수에 대해서는 덧셈의 뒷수, 즉 수조 중의 뒷수로 하고 이 수에 대해 정렬 삽입 조작을 한다. 즉, 수조 중의 앞의 두 수는 반드시 수조에 남은 수가 승차순으로 배열되고 그 다음에 끝까지 덧붙이기만 하면 된다.그리고 매번 덧붙인 것과 ans에 넣으면 됩니다. ans는 하프만 나무의 권한입니다.그 다음에 저는 문자열에 알파벳이 하나밖에 없는 상황을 처리하기 위해 가수를 한 개 더 늘리고 0을 설정합니다. 만약에 알파벳이 하나밖에 없다면 ans는 수조의 마지막 자모와 같을 것입니다. 만약에 한 자모가 아니라면 ans는 수조의 마지막 자모와 같지 않을 것입니다.