钓鱼 | FFY's Blog

题意

一条路上有$N$个鱼塘,鱼塘$i$花5$min$可以钓$t_i$条鱼,但每钓一次能钓到的鱼数量会减去$s_i$,并且从鱼塘$i$走到鱼塘$i+1$会花费$5\times dis_i$的时间.现在有$H$小时的时间,可以在任意鱼塘结束,求最多能钓多少条鱼

题解

非常巧妙的一道贪心题.
我们枚举结束的鱼塘,用总时间减去路上花掉的时间,剩下的时间用来钓鱼.
先将路上经过的鱼塘第一个5$min$能钓到的鱼条数加入优先队列,每次取出队列中最大元素的加入该鱼塘的答案,将该元素减去对应的$s_i$加入队列,直到时间用尽或者优先队列中最大值小于等于0,更新答案

• 注意时间的转化

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=110;
int n,h,dis[maxn],ans,bns;
int s[maxn],ss[maxn];
struct ffy
{
    int x,y;
    bool operator<(const ffy&a)
    const{return x<a.x;};
};
priority_queue<ffy>qq;
int main()
{
    scanf("%d%d",&n,&h);h*=12;
    for(int i=1;i<=n;i++)scanf("%d",&s[i]);
    for(int i=1;i<=n;i++)scanf("%d",&ss[i]);
    for(int i=2;i<=n;i++)scanf("%d",&dis[i]);
    for(int i=1;i<=n;i++)
    {
        h-=dis[i];int time=0;bns=0;
        for(int j=1;j<=i;j++)qq.push((ffy){s[j],j});
        while(++time<=h&&!qq.empty())
        {
            int a=qq.top().x;
            int b=qq.top().y;
            if(a<=0)break;
            bns+=a;
            qq.pop();
            qq.push((ffy){a-ss[b],b});
        }
        ans=max(ans,bns);
    }
    printf("%d\n",ans);
    return 0;
}