钓鱼

题目链接

思路分析

1. 　　题目要求所得总数最大，因此很显而易见地可看出是贪心。
2. 　　由于到每个池塘都有不同数目的鱼可钓，因此可以依次枚举最远到达第i个池塘时的情况；
3. 　　因为到达第i个池塘时必定经过前i-1个池塘，因此可以求出从1-i中每5分钟可钓出的鱼的数目，并进行从大到小排序，选择最大的鱼数目。
4. 　　注意点：
   1. H的时间有限，因此H>=0
   2. 每个池塘可钓出鱼数目最多只有Hi/5种（因为存在的d[i]=0的情况），且鱼的数目必须大于0

代码

 1 #include
 2 #include
 3 #include
 4 #include
 5 #include
 6 using namespace std;
 7 const int maxn=1e6+7;
 8 priority_queue<int> T;
 9 int N,H,t[maxn],f[maxn],d[maxn],Ans;
10 int main(void)
11 {
12     scanf("%d%d",&N,&H);
13     H*=60;
14     for(int i=1; i<=N; ++i)scanf("%d",&f[i]);
15     for(int i=1; i<=N; ++i)scanf("%d",&d[i]);
16     for(int i=2; i<=N; ++i)scanf("%d",&t[i]);
17     for(int i=1; i<=N; ++i)
18     {
19         H-=(5*t[i]);//到第i个池塘所剩时间
20         if(H<0)break;//如果H<0，说明到不了第i个池塘，可以退出 
21         int n=H/5,ans=0;
22         while(n--&&f[i]>0)
23         {
24             T.push(f[i]) ;
25             f[i]-=d[i];
26         }
27         n=H/5;
28         priority_queue<int> Q;//用大根堆，精简代码 
29         Q=T;
30         while(n--&&!Q.empty() )//注意可钓鱼的次数与 所能钓出的鱼的种数都是有限的 
31         {
32             ans+=Q.top() ;
33             Q.pop() ;
34         }
35         Ans=max(ans,Ans);//比较最远到达第i池塘时，所能钓到的最多的鱼 
36     }
37     printf("%d",Ans);
38     return 0;
39 }