1 条题解

  • 0
    @ 2024-10-29 10:32:20

    解析:

    依次枚举在前i个湖中钓鱼的情况;

    先减掉路上消耗的时间;

    选这i个湖中5分钟可以钓最多的鱼的湖钓5分钟,然后更新这个湖5分钟可以钓鱼的数量;

    直到时间消耗光;

    使用优先队列维护可钓鱼的湖;

    #include<bits/stdc++.h>
    using namespace std;
    int H,n;
    int t;//分钟数
    int a[105];//a[i]表示第i个湖第1个5分钟可以钓到鱼的数量
    int d[105];//d[i]表示第i个湖每5分钟钓鱼的减少数量
    int T[105];//T[i]表示从第i个湖到第i+1个湖所用的时间为5*T[i]
    struct node{
        int a;//当前5分钟可以钓鱼数量
        int d;//每5分钟减少数量
        //重置小于号运算符,钓鱼数量小的小
        bool operator < (const node &x) const{
            return a<x.a;
        }
    };
    priority_queue <node> q;//大根堆
    int ans=0;
    int main() {
        cin>>n>>H;
        t=H*60;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        for(int i=1;i<=n;i++){
            cin>>d[i];
        }
        for(int i=1;i<n;i++){
            cin>>T[i];
        }
        for(int i=1;i<=n;i++){//枚举钓鱼的湖的数量
            int t1=t;//时间
            for(int j=1;j<i;j++){//去掉走路用的时间
                t1-=T[j]*5;
            }
            while(!q.empty()){//清空优先队列
                q.pop();
            }
            for(int j=1;j<=i;j++){//枚举每个鱼塘
                node x;
                x.a=a[j];//当前鱼塘5分钟可以钓鱼数量
                x.d=d[j];//每5分钟减少数量
                q.push(x);
            }
            int sum=0;//钓鱼数量
            while (t1>=5){//只要时间大于等于5分钟,就可以钓鱼
                if (!q.empty()){//还有鱼塘可以钓到鱼
                    node x=q.top();//捡最多的钓
                    sum+=x.a;//钓鱼数量
                    t1-=5;//消耗5分钟
                    q.pop();//钓完弹出
                    x.a-=x.d;//计算这个鱼塘下五分钟可以钓鱼数量
                    if (x.a>0){//如果数量大于0
                        q.push(x);//加入优先队列
                    }
                }else{//如果没有能钓到鱼的鱼塘,退出循环
                    break;
                }
            }
            ans=max(ans,sum);//取最大值
        }
        cout<<ans;
        return 0;
    }

    信息

    ID
    605
    时间
    1000ms
    内存
    512MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者