首页 > 编程语言 >【算法】多路归并(鱼塘钓鱼)

【算法】多路归并(鱼塘钓鱼)

时间:2024-03-18 22:58:55浏览次数:24  
标签:11 归并 多路 钓鱼 int 钓到 鱼塘 spend

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

鱼塘编号12345
第1分钟能钓到的鱼的数量(1..1000)101420169
每钓鱼1分钟钓鱼数的减少量(1..100)24653
当前鱼塘到下一个相邻鱼塘需要的时间(单位:分钟)3544

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

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

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

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

输入格式

共 55 行,分别表示:

第 11 行为 N;

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

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

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

第 55 行为截止时间 T。

输出格式

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

数据范围

1≤N≤100
1≤T≤1000

输入样例:
5
10 14 20 16 9
2 4 6 5 3
3 5 4 4
14
输出样例:
76

分析:

 利用贪心思维,并不需要来回折返,如果钓完一分钟之后,这个鱼塘的鱼的数量依旧比其他鱼塘多,那就继续钓,这样可以节省来回的路上时间,使时间最大化

 

注意: 

(1)int spend[N]={0};

(2)memset(spend,0,sizeof(spend));

两个的区别:

第一行:

这行代码是在定义数组时使用的,不是赋值操作,切记切记!!!

而且也只是给第一个数组赋值为0

第二行:

这个函数是C中的,作用是将spend数组全部赋值为0

#include<iostream>
#include<cstring>
using namespace std;
#define N 110

int fishnum[N],d[N],dtime[N],spend[N];//鱼数,减少量,下个鱼塘时间,钓鱼所花时间

int get(int k){//求出鱼的数量
    return max(0,fishnum[k]-d[k]*spend[k]);
}

int work(int n,int T){
    int res=0;
    memset(spend,0,sizeof(spend));//将spend数组全部赋值为0
    for(int i=0;i<T;i++){
        int t=1;
        for(int j=2;j<=n;j++){//从第二个开始枚举鱼塘
            if(get(t)<get(j)){
                t=j;
            }
        }
        res+=get(t);//得到鱼的总数量
        spend[t]++;
    }
    return res;
}
int main(){
    int n,T;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>fishnum[i];
    for(int i=1;i<=n;i++) cin>>d[i];
    for(int i=2;i<=n;i++){
        cin>>dtime[i];
        dtime[i]+=dtime[i-1];//前缀和
    }
    cin>>T;
    int res=0;
    for(int i=1;i<=n;i++){
        res=max(res,work(i,T-dtime[i]));
    }
    cout<<res<<endl;
    return 0;
    
}

标签:11,归并,多路,钓鱼,int,钓到,鱼塘,spend
From: https://blog.csdn.net/weixin_74154742/article/details/136824449

相关文章

  • 【转载】Redis -- IO多路复用及redis6的多线程
    都知道redis是通过单线程+io多路复用来避免并发问题的,然后在redis6的时候redis引入了多线程,这里就来详细说说IO多路复用模型以及redis的多线程。Redis的I/O多路复用模型有效的解决单线程的服务端,使用不阻塞方式处理多个client端请求问题。在看I/O多路复用知识之前,我们先来......
  • 蓝桥杯算法集训 - Week 2:双指针、归并排序、多路归并
    蓝桥杯算法集训-Week2本系列随笔用于整理AcWing题单——《蓝桥杯集训·每日一题2024》的系列题型及其对应的算法模板。一、双指针Ⅰ、代码模板常见问题分类:(1)对于一个序列,用两个指针维护一段区间(2)对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作f......
  • 网络编程3 端口复用-多路IO转接select
    网络编程3端口复用-多路IO转接TCP状态转换图端口复用防止服务器重启时之前绑定的端口还未释放或者程序突然退出而系统没有释放端口。这种情况下如果设定了端口复用,则新启动的服务器进程可以直接绑定端口。如果没有设定端口复用,绑定会失败,提示ADDR已经在使用中。解决端口复用......
  • ffmpeg多路视频合并
    2,3,4路视频拼接可以参考下面:https://blog.csdn.net/tianshan2010/article/details/104737576https://blog.csdn.net/Gary__123456/article/details/887427054路拼接【上下左右】:ffmpeg-i1.mp4-i2.mp4-i3.mp4-i4.mp4-filter_complex"[0:v]pad=iw2:ih2[a];[a][1:v]ove......
  • 归并排序、快速排序——左神数据结构与算法Day2学习笔记C++版本(持续更新)
    递归行为        利用递归求整个数组的最大值,代码如下。intfind_Max(inta[],intL,intR){if(L==R){returna[L];}intmid=L+((R-L)>>1);//mid是数组的中点intleftMax=find_Max(a,L,mid);intrightMax......
  • 外部排序中多路归并排序,采用败者树比胜者树更优的原因和简易证明
    外部排序中多路归并排序,采用败者树较优的原因在外部排序中,多路归并排序采用败者树的优点主要有以下原因:多路归并排序过程多路归并是指对\(r\)个初始归并段,做\(k\)路平衡归并过程如下:每趟归并时,对\(k\)个已有序归并段进行归并第\(i\)个归并段最小值为\(X_i\),每次取\(X_j=\mi......
  • 力扣148排序链表--复习归并和快速排序
    递归的归并排序归并排序主要流程是拆分--排序--合并--排序--合并//拆分voidmergeSort(vector<int>&nums,intstart,intend){ if(start>=end)return; intmid=start+(end-start)/2; mergeSort(nums,start,mid); mergeSort(nums,mid+1,end); //最后一层排......
  • 基于 concept 的归并排序
    基于concept的归并排序template<std::random_access_iteratorRandomIter,std::random_access_iteratorRandomTempIter,typenameComp>requiresrequires(Compcomp,RandomIterit,RandomTempItertmp_it){{comp(*it,*it)}->std::same_as&......
  • 排序链表(自底向上归并排序)
    题目:时间复杂度:O(nlogn),空间复杂度:O(1)structListNode{intval;ListNode*next;ListNode():val(0),next(nullptr){}ListNode(int_val):val(_val),next(nullptr){}ListNode(int_val,ListNode*_next):val(_val),next(_next){}};class......
  • redis自学(15)IO多路复用
     无论是阻塞IO还是非阻塞IO,用户应用在一阶段都需要调用recvfrom来获取数据,差别在于无数据时的处理方案: 如果调用recvfrom时,恰好没有数据,阻塞IO会使进程阻塞,非阻塞IO使CPU空转,都不能充分发挥CPU的作用。 如果调用recvfrom时,恰好有数据,则用户进程可以直接进入第二阶段,读取并......