fish.c

ACM钓鱼问题算法 贪婪算法例子

#define   max   200 

int   h,n; 
int   fi[max],di[max],ti[max]; 
int   res[max],fish,resMax[max],fishMax; 

int   init(); 
void   done(); 
void   getFish(int   ,int); 

int   main(int   argc,   char   *argv[]) 
{ 
          int   i; 
          
          while(init()){ 
                  done(); 
            
            for(i=1;   i <n;   i++){ 
                      printf( "%d,   ",resMax[i]); 
            } 
            printf( "%d ",resMax[i]); 
            printf( "\n"); 
            printf( "Number   of   fish   expected:   %d\n\n",fishMax);         
            
          }             
      return   0; 
} 

void   getFish(int   lack,int   leftTime) 
{ 
          int   i,j,pos; 
          int   fi2[max]; 
          
          fish=0; 
          for(i=1;   i <=n;   i++){ 
                  fi2[i]=fi[i]; 
                  res[i]=0; 
          }       
          while(leftTime> 0){ 
    pos=1; 
                  for(i=1;   i <=lack;   i++){ 
                          if(fi2[pos] <fi2[i])   { 
                                  pos=i; 
                          }           
                  } 
                  if(fi2[pos]==0)break; 
                  fish+=fi2[pos]; 
                  res[pos]+=5; 
                  leftTime-=5; 
                  if(fi2[pos]> di[pos])   fi2[pos]-=di[pos]; 
                  else   fi2[pos]=0; 
          } 
          res[1]+=leftTime; 
}           

void   done() 
{ 
          int   i,j; 
          int   leftTime=h; 
          for(i=1;   i <=n;   i++){ 
                  if(leftTime <=ti[i-1]*5){ 
                          break; 
                  } 
                  leftTime-=ti[i-1]*5; 
                  getFish(i,leftTime); 
                  if(fish> fishMax)       { 
                          fishMax=fish; 
                          for(j=1;   j <=n;   j++){ 
                                  resMax[j]=res[j]; 
                          } 
                  }else   if(fish==fishMax){ 
                          for(j=1;   j <=n;   j++){ 
                                  if(resMax[j]> res[j])   break; 
                                  if(resMax[j] <res[j]){ 
                                          for(;j <=n;j++){ 
                                                  resMax[j]=res[j]; 
                                          }   
                                          break;         
                                  }           
                          }           
                  }           
          }           
          
}           

int   init() 
{ 
          int   i; 
          scanf( "%d ",&n); 
          if(n==0)   return   0; 
          scanf( "%d ",&h); 
          
          for(i=1;   i <=n;   i++){ 
                  scanf( "%d ",&fi[i]); 
                  resMax[i]=0; 
          } 
          for(i=1;   i <=n;   i++){ 
                  scanf( "%d ",&di[i]); 
          } 
          for(i=1;   i <=n-1;   i++){ 
                  scanf( "%d ",&ti[i]); 
          }   
          fishMax=0; 
          h=h*60; 
          ti[0]=0;       
            return   1;         
}