Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

好假

Posted by fuzigege at 2004-07-18 13:18:30 on Problem 1521
这个题目我在ZOJ上通过,在这里提交就超时。
程序中没有多大的循环呀,真是bt。
还是看看程序吧!
/* OnlinePID ZJU_1117 ( Entropy) */
/* Huffman 算法 */
#include <stdio.h>
#include <string.h>
#define INFINITY 99999999
typedef struct{
   int plink;
   int weight;
}Node;

Node node[60]; 
int  cc; /* character count */
int  orlen; /* ASCII bit len */ 

int input()
{
    char tmp[10000];  
    int  i, j;
    
    scanf("%s", tmp);
    if( strcmp(tmp, "END") == 0 ) return 0;
    
    for(i=0; i<=26; i++)
    { node[i].weight = 0; node[i].plink = -1; }
    
    for(i=0; tmp[i]; i++)
    {
       if( tmp[i] != '_' ) j = tmp[i]-'A';
       else                j = 26;
       node[j].weight++;   node[j].plink = 0;
    }
    
    for(orlen=cc=i=0; i<=26; i++) 
      if( node[i].weight != 0 )
      { orlen += node[i].weight * 8; cc++; }
    return 1;
}
int huffman()
{
    int i, j, rets, t;
    int w1, w2, x1, x2;
    
    for(i=1; i<=cc-1; i++)
    {
       /* select two small weight */
       w1 = w2 = INFINITY; x2 = x1 = 0;
       for(j=0; j<=26+i-1; j++)
        if(node[j].plink == 0)
        {
           if(node[j].weight < w1 )
           {  w2 = w1; x2 = x1;  w1 = node[j].weight; x1 = j; }
           else if(node[j].weight < w2)
           {  w2 = node[j].weight; x2 = j; }
        }
        
       /* Add a new node, which weight is w1+w2 */
       /* and set node x1, x2 's parent to new node */
       node[26+i].weight = w1 + w2; 
       node[26+i].plink = 0;      
       node[x1].plink = node[x2].plink = 26+i;
    }
    /* Calc every character node 's depth in huffman tree */
    /* and return sum of them */
    for(rets=i=0; i<=26; i++)
    {
       j = i; t = 0;
       while(node[j].plink != 0)
       {  t++; j=node[j].plink; }
       rets += node[i].weight * t;
    }
    return rets;
}
    
int main()
{
    int oplen;
    while( input() )
    {
       if(cc==1) oplen = orlen/8;
       else oplen = huffman();
       printf("%d %d %.1lf\n", orlen, oplen, (double)orlen/oplen);
    }
    return 0;
}
     

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator