鱼塘钓鱼

题目 鱼塘钓鱼

思路分析

贪心贪过头了 想着一步到位

当时是看出来了 每次选择最优的地方钓 多路归并 但是它有一个问题是 从一个鱼塘挪动到另一个鱼塘是需要成本的（时间会减少） 于是陷入死胡同 要是把这个消耗的时间抵扣到下一个鱼塘可钓的鱼里面 问题就变得复杂起来了 权值一直在变动

其实这题还有一层贪心在外面

要把不影响的因素全都拿出来——最后要的钓鱼总数最大 只与钓鱼的总时间的分配有关 这里才是多路归并 其他的移动时间 鱼塘选择都是间接相关的

鱼塘选择方面 首先能贪心确定的是 只会往一个方向走 不会反复横跳 可以采用枚举的方式——只在前k的鱼塘里钓鱼 能钓到的最大值 最后再把他们综合取个max

把要用到的前k个鱼塘确定了 那么钓鱼的时间也就确定出来了——总时间 减去 移动所消耗的时间

那么才是 用多路归并思想 合理分配这些钓鱼时间 使得总价值最大

代码实现

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

const int N=110;

int Begin[N],del[N],spend[N];

int n,T;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++)

        cin>>Begin[i];

    for(int i=1;i<=n;i++)

        cin>>del[i];

    for(int i=2;i<=n;i++){

        int t;cin>>t;

        spend[i]=spend[i-1]+t;//构造前缀和 到达第i个鱼塘所共需时间

    }

    cin>>T;

    int res=0;

    for(int i=1;i<=n;i++){

        int fishtime=T-spend[i];

        priority_queue<PII> fishchose;

        for(int j=1;j<=i;j++)

            fishchose.push({Begin[j],j});

        int fishcnt=0;

        while(!fishchose.empty() && fishtime>0){

            auto fish=fishchose.top();

            fishchose.pop();

            int id=fish.second;

            fishcnt+=fish.first;

            fishtime--;

            fish.first-=del[id];

            if(fish.first>0)

                fishchose.push({fish.first,id});

        }

        res=max(res,fishcnt);

    }

    cout<<res;

    return 0;

}

同类题型

视频讲解

⬅️ 超级丑数 🏠 00-刷题理模型 ➡️ （50分 多路归并 二分）技能升级