第1部分 基础算法(提高篇)--第1章 贪心算法1431：钓鱼

1431：钓鱼

时间限制: 1000 ms 内存限制: 65536 KB
提交数: 936 通过数: 444
【题目描述】
在一条水平路边，有 n 个钓鱼湖，从左到右编号为 1,2,…,n。佳佳有 H 个小时的空余时间，他希望利用这个时间钓到更多的鱼。他从 1 出发，向右走，有选择的在一些湖边停留一定的时间（是 5 分钟的倍数）钓鱼。最后在某一个湖边结束钓鱼。佳佳从第 i 个湖到第 i+1 个湖需要走 5×Ti分钟路，还测出在第 i 个湖停留，第一个 5 分钟可以钓到 Fi​​ 条鱼，以后每再钓 5 分钟，可以钓到的鱼量减少 Di​​ ，若减少后的鱼量小于 0，则减少后的鱼量为 0 。为了简化问题，佳佳假定没有其他人钓鱼，也没有其他因素影响他钓到期望数量的鱼。请编程求出佳佳最多能钓鱼的数量。

【输入】
第一行一个整数 n，表示湖的个数

第二行一个整数 H，表示佳佳的空闲时间

第三行有 n 个整数，依次表示每个湖第一个 5 分钟能钓到鱼的数量

第四行有 n 个整数，依次表示以后的每5分钟钓鱼数量比前一个 5 分钟钓鱼数量减少的数量

第五行有 n−1 个整数，Ti 表示由第 i 个湖到第 i+1 个湖需要花 5×Ti分钟的路程

【输出】
输出只有一行，表示佳佳最多能钓鱼的数量。

【输入样例】
3
1
4 5 6
1 2 1
1 2
【输出样例】
35
【提示】
样例解释:

在第 1 个湖钓 15 分钟，共钓得 4+3+2=9 条鱼；

在第 2 个湖钓 10 分钟，共钓得 5+3=8 条鱼；

在第 3 个湖钓 20 分钟，共钓得 6+5+4+3=18 条鱼；

从第 1 个湖到第 2 个湖，从第 2 个湖到第 3个湖，共用时间 15 分钟，共得 35 条鱼，并且这是最多的数量。

---

思路：第一步：首先设所有的时间全部转化为5分钟来计算，如一个小时有12个5分钟 ，钓鱼一次使用的第一个五分钟直接减1。
　　第二步：1、以第i个池塘来计算。
　　　　　　2、到第i个池塘必须要先扣除路程中要花费的5分钟，然后再进行钓鱼，用优先队列存放每一个池塘当前钓鱼的个数，如果选择了第 j 个池塘钓鱼后，要更新第 j 个池塘的 钓鱼的数量，会优先压入队列中。
　　第三步：不断执行第二步2，直到时间为 0 ，或者优先队列中的所有的钓鱼量<=0 时则跳出，然后更新答案，返回第二步1.

 #include<iostream>
 #include<cstdio>
 #include<queue>
 #include<algorithm>
 #include<cstring>
 using namespace std;
 const int N = 110;
 int dis[N],n,h;
struct Node {
     int Fish , Dec ;
     bool operator < ( const Node & rhs ) const {
         return Fish < rhs.Fish ;
     }
 }a[N];
 

 int main()
 {
     scanf("%d%d",&n,&h);
     for (int i=1;i<=n;i++) scanf("%d",&a[i].Fish);
     for (int i=1;i<=n;i++) scanf("%d",&a[i].Dec);
     for (int i=2;i<=n;i++) scanf("%d",&dis[i]);
 
     h *= 12 ;
 
     int sum = 0 , ans = 0 ;
     for ( int i = 1 ; i <= n ; i++ ){
         h -= dis[i] ;
         sum = 0 ;
         priority_queue < Node > q ;
         for ( int j = 1 ; j <= i ; j++ ){
             q.push ( a[j] ) ;
         }
         int time = h ;
         while ( time > 0 ){
             Node cur = q.top() ;
             q.pop() ;
 
             if( cur.Fish <= 0 )
                 break ;
 
             sum += cur.Fish ;
             time -- ;
 
             cur.Fish -= cur.Dec;
             q.push(cur);
         }
         ans = max ( ans , sum ) ;
    }
     printf("%d\n",ans);
     return 0;
 }