钓鱼.c

算法分析ACM题目：湖边钓鱼算法 保证能运行！算法分析课程必备！

#include <stdio.h>

#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()!=0){
         done();
      
      for(i=1; i<n; i++){
           printf("%d,",resMax[i]);
      }
      printf("%d",resMax[i]);
      printf("\n");
      printf("Number of fish expected:%d\n",fishMax);    
      
     }      
   return 0;
}

void getFish(int lack,int leftTime)
{
     int i,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 n;    
}