首页 > 代码库 > Poj 1042 gone fishing

Poj 1042 gone fishing

2024-07-15 07:56:37   211人阅读

【题目大意】

题目就是在给定钓鱼时间，湖泊之间转移的时间，各湖泊初始鱼量，各湖泊鱼量的下降指数求在规定时间内的最大钓鱼量。

【解题思路】

本题目采用枚举+贪心的方法可以求解出来。首先我们需要对题目进行一些改造，我们需要枚举从第一个湖泊到第n个湖泊之间各种可能情况，然后再这些情况中选出最大值，输出结果。由于到各个湖泊的时间有所差异，我们首先需要把耽搁在转移路径上的时间除去，然后在剩余时间内确定钓鱼量的最大值，对于每次选择，我们采用贪心的方式选取最大值，进而得出最优解。

本题目需要特别注意输出格式，容易出现小错误：

我们需要考虑flag=0的情况，下面我们看一组数据：

*        看数据：
 *        2
 *        1
 *        0 0
 *        1 1
 *        1
 *        答案：
 *        60 0
 *        0
这里如果不写出代码：
          if(flag == 0)
          {60             printf("%d", hour*5);61             for(int i=1; i<n; i++)62                 printf(", %d", 0);63             printf("\nNumber of fish expected: %d\n\n", flag);64         }
那么最后会一直wrong answer。

【AC代码】

 1 #include<stdio.h> 2 struct lake 3 { 4     int fish; 5     int decrease; 6     int time; 7     int stay; 8 } K[30]; 9 int main()10 {11     int k_fish[30],k_stay[30],T[30];//T[i]表示路上花去时间12     int sum,maxn,flag,i,j,p,t,n,hour,k;13     while(scanf("%d",&n)&&n!=0)14     {15         //第一步的输入数据16         int hour;17         scanf("%d",&hour);18         hour*=12;19         for(int i=0;i<n;i++)20         {21             scanf("%d",&K[i].fish);22             k_fish[i]=K[i].fish;//复制数组方便枚举各种情况时还原K[i].fish23         }24         for(int i=0;i<n;i++)25         scanf("%d",&K[i].decrease);26         K[0].time=0;27         for(int i=1;i<=n-1;i++)28         scanf("%d",&K[i].time);29        T[0]=K[0].time;30        flag=0;//初始化最大值31         for(int i=0;i<n;i++)32         {33             if(i)34             T[i]=T[i-1]+K[i].time;//在转移过程中所消耗的时间35             for(int s=0;s<n;s++)36             {K[s].fish=k_fish[s];K[s].stay=0;}//每一次枚举都初始化数据，并把在每一个lake的时间置为037             sum=0;38             for(int h=1;h<=hour-T[i];h++)//在规定的时间内获取最大值39             {40                 maxn=0;41                 for(int k=0;k<=i;k++ )//寻找单位时间内最大的钓鱼量42                 {43                     if(maxn<K[k].fish){maxn=K[k].fish;p=k;}44                 }45                 sum+=maxn;46                 if(maxn>0)47                 {48                     K[p].fish-=K[p].decrease;K[p].stay++;//在最大值的地方加上滞留时间，并把鱼量减小49                  }50                  else K[0].stay++;//如果没有找到，则在第一个湖那边加1；51 52             }53             if(sum>flag)54             {flag=sum;55              for(int j=0;j<=n;j++)56              k_stay[j]=K[j].stay*5;  //这里只对全部鱼量不全为0的情况，故下面在输出结果时要考虑flag是否为057             }58         }59         if(flag == 0){60             printf("%d", hour*5);61             for(int i=1; i<n; i++)62                 printf(", %d", 0);63             printf("\nNumber of fish expected: %d\n\n", flag);64         }65         else{66        for(j=0;j<n-1;j++)67             printf("%d, ",k_stay[j]);68             printf("%d\n",k_stay[n-1]);69        printf("Number of fish expected: %d\n\n",flag);//注意输出格式70     }71     }72     return 0;73 }

 


联系
我们