钓鱼

https://loj.ac/problem/10009

题目描述

  有n个鱼塘，每个鱼塘有两个量，一个是初始每时刻能钓到的鱼的数量，还有一个是每钓一段时间每时刻能钓到鱼的数量的减少量。两两鱼塘之间有一定的距离，求在t时间最多钓到多少鱼

思路

  这题的做法比较多，主流以贪心和(dp)为主，这里就讲贪心。首先这个(5)分钟可以直接看做一个刻度，先与处理掉。在考虑每个鱼塘的情况，由于往返两个鱼塘的耗时难以确定，但我们假设已知最优解，那么最优解一定不会往返走，也就是说，一定是在一个鱼塘钓到一定数量的鱼在离开。所以我们只需算一次跨越鱼塘的花费，之后就可以“(0)”的往返了。有了这个贪心策略，我们就可以循环(i)从(1sim n)，表示在(1sim i)个鱼塘中最多钓到的个数，在维护一个优先队列表示目前一个时刻最多钓到的鱼的个数，去那里钓鱼并将新的数目加入队列。

代码

#include <bits/stdc++.h>
using namespace std;
struct aa
{
    int s,t;
    bool operator <(const aa &x)const
    {
        return s<x.s;
    }
}a[110];
int l[110];
priority_queue<aa>q;
int main() 
{
    int n,h;
    scanf("%d%d",&n,&h);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].s);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].t);
    for(int i=2;i<=n;i++)
        scanf("%d",&l[i]);
    h=h*12;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        h-=l[i];
        int m=h,sum=0;
        for(int j=1;j<=i;j++)
            q.push(a[j]);
        while(m>0)
        {
            aa p=q.top();q.pop();
            if(p.s<=0)break ;
            sum+=p.s;
            p.s-=p.t;
            q.push(p);
            m--;
        }
        ans=max(ans,sum);
    }
    printf("%d",ans);
    return 0;
}