当前位置：首页 > article >正文

鱼塘钓鱼（多路归并，贪心）

article 2025/2/11 19:08:59

题目：

1262. 鱼塘钓鱼

题目
提交记录
讨论
题解
视频讲解

有 NN 个鱼塘排成一排，每个鱼塘中有一定数量的鱼，例如：N=5N=5 时，如下表：

鱼塘编号	1	2	3	4	5
第1分钟能钓到的鱼的数量（1..1000）	10	14	20	16	9
每钓鱼1分钟钓鱼数的减少量（1..100)	2	4	6	5	3
当前鱼塘到下一个相邻鱼塘需要的时间（单位：分钟）	3	5	4	4

即：在第 11 个鱼塘中钓鱼第 11 分钟内可钓到 1010 条鱼，第 22 分钟内只能钓到 88 条鱼，……，第 55 分钟以后再也钓不到鱼了。

从第 11 个鱼塘到第 22 个鱼塘需要 33 分钟，从第 22 个鱼塘到第 33 个鱼塘需要 55 分钟，……

给出一个截止时间 TT，设计一个钓鱼方案，从第 11 个鱼塘出发，希望能钓到最多的鱼。

假设能钓到鱼的数量仅和已钓鱼的次数有关，且每次钓鱼的时间都是整数分钟。

输入格式

共 55 行，分别表示：

第 11 行为 NN；

第 22 行为第 11 分钟各个鱼塘能钓到的鱼的数量，每个数据之间用一空格隔开；

第 33 行为每过 11 分钟各个鱼塘钓鱼数的减少量，每个数据之间用一空格隔开；

第 44 行为当前鱼塘到下一个相邻鱼塘需要的时间；

第 55 行为截止时间 TT。

输出格式

一个整数（不超过231−1231−1），表示你的方案能钓到的最多的鱼。

数据范围

1≤N≤1001≤N≤100,
1≤T≤10001≤T≤1000

输入样例：

5
10 14 20 16 9
2 4 6 5 3
3 5 4 4
14

输出样例：

代码：

#include <bits/stdc++.h>
using namespace std;

const int N=110;

int a[N],d[N],l[N],spend[N];
//a每个鱼塘的初始值，d每分钟减少次数,l鱼塘间距,spend在改鱼塘的钓鱼数量

int get(int k){//当前时刻k鱼塘鱼的数量
    return max(0,a[k]-d[k]*spend[k]);
}

int work(int n,int T){
    memset(spend,0,sizeof spend);
    int res=0;
    for(int i=1;i<=T;i++){//遍历每个时刻
        int t=1;//存放当前时刻鱼数量最大的一个鱼塘
        for(int j=2;j<=n;j++){//遍历每个鱼塘，找出此时刻鱼塘数量最大的鱼塘t
            if(get(j)>get(t)){
                t=j;
            }
        }
        res+=get(t);//将t鱼塘此刻（第一个）鱼的数量加入到答案中
        spend[t]++;//在t鱼塘呆的时间加1
    }
    return res;
}

int main(){
    int n;
    scanf("%d",&n);
    
    //直线一定是最优解（反复横跳会浪费路上的时间），所以一共有n种路线，1，1-2，1-3，1-4
    
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&d[i]);
    for(int i=2;i<=n;i++) {
        scanf("%d",&l[i]);//从第二个位置开始存，存与前一个鱼塘的距离
        l[i]=l[i-1]+l[i];//把直线的路线也求一下
    }
    int T;
    scanf("%d",&T);
    int res=0;
    for(int i=1;i<=n;i++){
        res=max(res,work(i,T-l[i]));//传入走到最后一个鱼塘i，和钓鱼时间
    }
    
    printf("%d",res);
    
    return 0;
}