HDU 2527: 안전 하거나 안전 하지 않 음 (하 프 만 트 리)

Problem Description
자바 c + + 하루 컴퓨터 책 을 보다 가 재 미 있 는 것 을 봤 어 요!모든 문 자 는 숫자 로 인 코딩 되 어 정 보 를 저장 할 수 있 지만 서로 다른 인 코딩 방식 으로 얻 은 저장 공간 은 다르다!그리고 저장 공간 이 일정한 값 보다 클 때 안전 하지 않 습 니 다!그래서 자바 c + 는 문자 인 코딩 의 최소 공간 값 을 얻 을 수 있 는 방법 이 있 는 지 생각 합 니 다!분명히 이것 은 가능 하 다. 왜냐하면 책 에 이런 내용 이 있 기 때문이다. 하 프 만 코드 (Huffman Coding).한 자모의 가중치 는 문자열 에 나타 나 는 주파수 와 같다.그래서 자바 c + 는 보안 수치 와 문자열 을 주 고 이 문자열 이 안전 한 지 판단 하 는 데 도움 을 주 고 싶 습 니 다.
 
Input
여러 개의 케이스 를 입력 하 십시오. 먼저 하나의 숫자 n 은 n 개의 데이터 가 있 음 을 표시 합 니 다. 그 다음 에 각 그룹의 데 이 터 는 하나의 수치 m (integer) 가 있 고 문자열 과 빈 칸 이 없 으 며 소문 자 만 포함 되 어 있 습 니 다!
 
Output
문자열 의 인 코딩 값 이 주어진 값 보다 작 으 면 yes 를 출력 합 니 다. 그렇지 않 으 면 no 를 출력 합 니 다.
 
Sample Input

   
   
   
   

    
    
    
    2
12
helloworld
66
ithinkyoucandoit
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    no
yes
   
   
   
   

 
간단 한 하 프 만 나 무 는 처음에 제목 의 뜻 을 이해 하지 못 했다. 다른 사람 이 나 에 게 제목 의 뜻 을 알려 주 었 는데 원래 이렇게 간단 한 하 프 만 나무 일 뿐 이 었 다. 제목 은 잎 노드 를 제외 한 모든 노드 의 가중치 의 합 을 요구 하 는 것 이 었 다. 마침 데이터 구 조 는 하 프 만 나 무 를 배 웠 고 뜨 거울 때 철 을 두 드 렸 다.
주의해 야 할 것 은 문자 가 한 가지 밖 에 없 는 상황 에서 하 프 만 나 무 는 만 들 수 없 으 므 로 특수 처리 해 야 한 다 는 것 이다.
 

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int L = 1000000+10;
const int inf = 1<<30;
char str[L];
struct kode
{
    int num;
    char c;
} b[L<<2];

struct node
{
    int wei,parent,lson,rson,cover;
    char data;
} a[L<<2];

int main()
{
    int i,j,sum,t,len,lb;
    char ch;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%s",&sum,str);
        len = strlen(str);
        sort(str,str+len);
        for(i = 0; i<len<<2; i++)
        {
            a[i].cover = a[i].lson = a[i].rson = a[i].parent = a[i].wei = b[i].num = 0;
            a[i].data = b[i].c = '\0';
        }
        lb = 0;
        b[lb].num = 1;
        b[lb].c = ch = str[0];
        for(i = 1; i<len; i++)
        {
            if(str[i] == ch)
                b[lb].num++;
            else
            {
                lb++;
                ch = str[i];
                b[lb].c = ch;
                b[lb].num = 1;
            }
        }
        if(lb == 0)//         ，    
        {
            if(b[lb].num<=sum)
                printf("yes
");
            else
                printf("no
");
            continue;
        }
        lb++;
        int m = lb*2-1;
        for(i = 0; i<lb; i++)
        {
            a[i].data = b[i].c;
            a[i].wei = b[i].num;
        }
        for(i = 0; i<lb; i++)//      
        {
            int m1 = inf,m2 = inf;
            int x = 0,y = 0;
            for(j = 0; j<lb+i; j++)
            {
                if(a[j].wei<m1 && !a[j].cover)
                {
                    m2 = m1;
                    m1 = a[j].wei;
                    y = x;
                    x = j;
                }
                else if(a[j].wei<m2 && !a[j].cover)
                {
                    m2 = a[j].wei;
                    y = j;
                }
            }
            a[x].parent = lb+i;
            a[y].parent = lb+i;
            a[lb+i].lson = x;
            a[lb+i].rson = y;
            a[lb+i].wei = a[x].wei+a[y].wei;
            a[x].cover = a[y].cover = 1;
        }
        int ans = 0;
        for(i = lb; i<2*lb-1; i++)//                  
            ans+=a[i].wei;
        if(ans<=sum)
            printf("yes
");
        else
            printf("no
");
    }

    return 0;
}