信息学奥赛一本通 1373:鱼塘钓鱼(fishing) 第三章 树

1373:鱼塘钓鱼(fishing)

时间限制: 1000 ms         内存限制: 65536 KB

【题目描述】

有N个鱼塘排成一排(N<100),每个鱼塘中有一定数量的鱼,例如:N=5时,如下表:

鱼塘编号                                                                        1        2        3        4        5

每1分钟能钓到的鱼的数量(1..1000)                        10      14      20       6        9

每1分钟能钓鱼数的减少量(1..100)                           2        4        6        5        3        

当前鱼塘到下一个相邻鱼塘需要的时间(单位:分钟)3        5        4        4

即:在第1个鱼塘中钓鱼第1分钟内可钓到10条鱼,第2分钟内只能钓到8条鱼,……,第5分钟以后再也钓不到鱼了。从第1个鱼塘到第2个鱼塘需要3分钟,从第2个鱼塘到第3个鱼塘需要5分钟,……

给出一个截止时间T(T<1000),设计一个钓鱼方案,从第1个鱼塘出发,希望能钓到最多的鱼。

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

【输入】

共5行,分别表示:

第1行为N;

第2行为第1分钟各个鱼塘能钓到的鱼的数量,每个数据之间用一空格隔开;

第3行为每过1分钟各个鱼塘钓鱼数的减少量,每个数据之间用一空格隔开;

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

第5行为截止时间T。

【输出】

一个整数(不超过2^31−1),表示你的方案能钓到的最多的鱼。

【输入样例】

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

【输出样例】 

76

解析:

枚举在前i个鱼塘钓鱼的情况;

使用大根堆保存所有鱼塘当前一分钟可以钓鱼的数量,取堆顶,即当前分钟可以钓到鱼的最多数量,钓完将该鱼塘下一分钟能钓到的鱼数量入堆。

详见代码:

#include<bits/stdc++.h>
using namespace std;
int n,t;
int f[105];//第i个鱼塘第一分钟钓鱼数量
int s[105];//每分钟钓鱼减少量
int nt[105];//到下一个鱼塘时间
int rt;//路上消耗时间
int ans=0;
struct node {//钓鱼
    int id;//鱼塘ID
    int num;//钓鱼数量
};
struct big{//大根堆比较仿函数
    bool operator() (const node x,const node y){
        return x.num<y.num;
    }
};
priority_queue <node,vector<node>,big> pq;//大根堆
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>f[i];
    }
    for (int i=1;i<=n;i++){
        cin>>s[i];
    }
    for (int i=2;i<=n;i++){
        cin>>nt[i];
    }
    cin>>t;
    rt=0;
    for(int i=1;i<=n;i++){//枚举在前i个鱼塘钓鱼的情况
        int sum=0;//当前钓鱼数量
        rt+=nt[i];//计算路上花费的时间
        node tmp;//临时变量
        while (!pq.empty()) pq.pop();
        for(int j=1;j<=i;j++){//前i个鱼塘入堆
            tmp.id=j;
            tmp.num=f[j];
            pq.push(tmp);
        }
        for(int j=rt+1;j<=t;j++){//枚举可以钓鱼的时间
            if (pq.empty()) break;//无鱼可钓,退出
            tmp=pq.top();//取堆顶钓鱼最多
            pq.pop();
            sum+=tmp.num;//计算钓鱼数量
            tmp.num-=s[tmp.id];//该鱼塘钓鱼数量减少
            if (tmp.num>0){//还能钓到鱼
                pq.push(tmp);//入堆继续
            }
        }
        ans=max(ans,sum);//取最大值
    }
    cout<<ans;
    return 0;
}

最近更新

  1. leetcode705-Design HashSet

    2024-04-03 12:46:01       5 阅读
  2. Unity发布webgl之后打开streamingAssets中的html文件

    2024-04-03 12:46:01       5 阅读
  3. vue3、vue2中nextTick源码解析

    2024-04-03 12:46:01       6 阅读
  4. 高级IO——React服务器简单实现

    2024-04-03 12:46:01       5 阅读
  5. 将图片数据转换为张量(Go并发处理)

    2024-04-03 12:46:01       4 阅读
  6. go第三方库go.uber.org介绍

    2024-04-03 12:46:01       6 阅读
  7. 前后端AES对称加密 前端TS 后端Go

    2024-04-03 12:46:01       7 阅读

热门阅读

  1. IPKISS ------ 导入 Lumerical S-matrix 仿真结果

    2024-04-03 12:46:01       2 阅读
  2. Gtest 和VLD一起使用报内存泄漏

    2024-04-03 12:46:01       2 阅读
  3. Nginx的常用命令以及配置文件“nginx.conf”的解读

    2024-04-03 12:46:01       3 阅读
  4. 动态加载json文件

    2024-04-03 12:46:01       4 阅读
  5. 卷积神经网络

    2024-04-03 12:46:01       2 阅读
  6. python项目练习——12.在线购物商城应用程序

    2024-04-03 12:46:01       4 阅读
  7. 微知识-git rebase常用的3个场景和2个本质

    2024-04-03 12:46:01       3 阅读
  8. linux tasklet

    2024-04-03 12:46:01       4 阅读
  9. BabyAGI源码解读(2)-核心agents部分

    2024-04-03 12:46:01       4 阅读
  10. C# 各种数据结构定义以及初始化

    2024-04-03 12:46:01       4 阅读