算法设计 || 第5题:钓鱼问题-北京大学网站在线算法题(贪心算法)

这篇具有很好参考价值的文章主要介绍了算法设计 || 第5题:钓鱼问题-北京大学网站在线算法题(贪心算法)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

(一)题目网址+视频网址 

(二)手写草稿思考

Part1: 慕课PPT

 Part2: 笨蛋的学习


(一)题目网址+视频网址 

北京大学网站在线算法题:1042 -- Gone Fishing (poj.org)

视频讲解(北京大学附郭炜教授) :程序设计与算法(二)算法基础_北京大学_中国大学MOOC(慕课) (icourse163.org)

(二)手写草稿思考

Part1: 慕课PPT

老师的视频讲解,发现老师好可爱的啊!居然去旅行的时候背着旅行包拍这种推广算法的视频!

算法设计 || 第5题:钓鱼问题-北京大学网站在线算法题(贪心算法)

算法设计 || 第5题:钓鱼问题-北京大学网站在线算法题(贪心算法)

算法设计 || 第5题:钓鱼问题-北京大学网站在线算法题(贪心算法)

算法设计 || 第5题:钓鱼问题-北京大学网站在线算法题(贪心算法)

 Part2: 笨蛋的学习

算法设计 || 第5题:钓鱼问题-北京大学网站在线算法题(贪心算法)

 说实话,我在看完老师的视频后,依旧对题意还没有非常理解,呜呜,救救我!

一个相关的大佬分析:(372条消息) 鱼塘钓鱼 贪心算法_小王不头秃的博客-CSDN博客

然后又仔细地研究了一下题目的意思+输入输出是个啥:算法设计 || 第5题:钓鱼问题-北京大学网站在线算法题(贪心算法)

//Molly
#include<iostream>    // 引入输入输出流库
#include<string>      // 引入字符串库
#include<map>         // 引入映射库
#include<vector>      // 引入向量库
#include<algorithm>   // 引入算法库
#include<stdio.h>     // 引入标准输入输出库
#include<cstring>     // 引入字符串库
#include<stdlib.h>    // 引入标准库
#include<sstream>     // 引入字符串流库
#include<set>         // 引入集合库
#include<cmath>       // 引入数学库

// 定义 long long 类型为 n
typedef long long n;

using namespace std;

// 定义结构体,储存每个湖的鱼数以及每个时间片钓鱼的情况
struct node1
{
    int fishnum; // 鱼的数量
    int time[30]; // 每个时间片钓鱼情况
};

// 定义结构体,储存每次钓鱼的湖泊编号、时间片数以及鱼的数量
struct node2
{
    int F; // 鱼的数量
    int no; // 湖泊编号
    int k; // 时间片数
};

// 定义排序规则,按照鱼的数量从大到小排序,用于 node1 结构体的排序
struct rule1
{
    bool operator()( const node1 &t1,const node1 &t2)
    {
        return t1.fishnum>t2.fishnum;
    }
};

// 定义排序规则,按照鱼的数量从大到小排序,用于 node2 结构体的排序
struct rule2
{
    bool operator()(const node2 &t1,const node2 &t2)
    {
        return t1.F>t2.F;
    }
};

int maxfish; // 最大的鱼数

int main()
{
    ios::sync_with_stdio(false); // 关闭同步流,提高输入输出速度
    int n; // 湖泊的数量
    while(cin>>n&&n) // 不断输入湖泊数量,直到输入 0 结束
    {
        node1 a[30]; // 定义 node1 数组,储存每个湖的钓鱼情况
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
                a[i].time[j]=0;
        }
        int h; // 每个时间片的时长
        maxfish=0; // 最大鱼数初始化为 0
        int f[30]; // 每个湖泊的初始鱼数
        int d[30]; // 每个湖泊每次钓鱼能够得到的鱼数
        int t[30]; // 到达每个湖泊需要的时间
        
        cin>>h;
        for(int i=1;i<=n;i++) cin>>f[i]; // 输入每个湖泊的初始鱼数
        for(int i=1;i<=n;i++) cin>>d[i]; // 输入每个湖泊每次钓鱼能够得到的鱼数
        t[0]=0; // 到达第一个湖的时间为 0
        for(int i=1;i<n;i++) cin>>t[i]; // 输入到达每个湖泊所需的时间
        int k=0; // 定义时间片个数
        for(int x=1;x<=n;x++) // 枚举最终停下来的湖
        {
            int walktime=0; // 走路用的时间片
            for(int j=1;j<x;j++)
                walktime+=t[j];
            k=h*12-walktime; // 根据题意计算可用的时间片数
            node2 m[5000]; // 定义 node2 数组,储存所有的钓鱼情况
            int kase=0; // 钓鱼情况的数量
            int number=0; // 钓鱼得到的鱼数
            for(int i=1;i<=x;i++)
                for(int j=1;j<=k;j++)
                {
                    number=f[i]-(j-1)*d[i]; // 计算钓鱼得到的鱼数
                    if(number>0)
                    {
                        m[kase].F=number; // 储存鱼的数量
                        m[kase].no=i; // 储存湖泊编号
                        m[kase].k=j; // 储存时间片数
                        kase++;
                    }
                    else
                    {
                        m[kase].F=0; // 鱼的数量为 0
                        m[kase].no=i; // 储存湖泊编号
                        m[kase].k=j; // 储存时间片数
                        kase++;
                    }
                }
            stable_sort(m,m+kase,rule2()); // 对 m 数组进行排序
            int num=0; // 钓鱼得到的总鱼数
            for(int i=0;i<k;i++)
                num+=m[i].F;
            a[x].fishnum=num; // 储存钓鱼得到的总鱼数
            for(int i=0;i<k;i++)
            {
                for(int j=1;j<=x;j++)
                {
                    if(m[i].no==j)
                    {
                        if(m[i].k>a[x].time[j])
                            a[x].time[j]=m[i].k;
                    }
                }
            }
        }
        sort(a+1,a+1+n,rule1()); // 对 a 数组进行排序
        for(int i=1;i<=n;i++)
        {
            if(i==n)
                cout<<a[1].time[i]*5<<endl; // 输出最短时间
            else
                cout<<a[1].time[i]*5<<", ";
        }
        cout<<"Number of fish expected: "<<a[1].fishnum<<endl<<endl; // 输出钓鱼得到的总鱼数
    }
    return 0; // 程序结束
}

算法设计 || 第5题:钓鱼问题-北京大学网站在线算法题(贪心算法)

算法设计 || 第5题:钓鱼问题-北京大学网站在线算法题(贪心算法)文章来源地址https://www.toymoban.com/news/detail-449229.html

到了这里,关于算法设计 || 第5题:钓鱼问题-北京大学网站在线算法题(贪心算法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数字电路与系统】【北京航空航天大学】实验:时序逻辑设计——三色灯开关(二)、需求分析和系统设计

    本次实验(一)见博客:【数字电路与系统】【北京航空航天大学】实验:时序逻辑设计——三色灯开关(一)、实验指导书 说明 :本次实验的代码使用verilog编写,文章中为阅读方便,故采用matlab代码格式。 2.1、需求分析 本次实验要求设计一种通过操作开关的时间控制灯

    2024年04月26日
    浏览(45)
  • 23北京邮电大学备考经验

    初试成绩: 总体:浙江某双非学校的软件工程专业、综合测评成绩班级前两名、浙江省省级优秀毕业生、发表过论文、参加过不少学科竞赛 英语成绩:高中有过全国中学生英语能力竞赛国二、参加过全国大学生英语能力竞赛(两次,但都是仅有参赛奖,主要是自己自认为英

    2023年04月09日
    浏览(42)
  • 记一次北京某大学逻辑漏洞挖掘

    0x01 信息收集 个人觉得教育src的漏洞挖掘就不需要找真实IP了,我们直接进入正题,收集某大学的子域名,可以用oneforall,这里给大家推荐一个在线查询子域名的网站:https://www.virustotal.com/ 收集到的子域名还是蛮多的,主要是子域名直接就可以复制到txt文件,方便后续域名探

    2024年04月28日
    浏览(40)
  • 北京大学计算机网络lab1——MyFTP

    目录 Lab目标 一、知识补充 二、具体实现 1.数据报文格式和字符串处理 2.open函数 3.auth 4.ls 5.get和put 三、总结 ps:本人靠着计网lab几乎就足够在就业行情并不好的23年找到自己满意的工作了,计网lab的教程也非常给力,对我这种恐惧写lab的菜狗都非常友好(本人写lab3确实比较

    2024年02月07日
    浏览(47)
  • 北京大学2014计算机学科夏令营上机考试

    暴力必超时  利用栈的思想,利用一个(模仿栈)的数组,遇到男孩则入栈(即加入数组),记录当前位置(更新相对下标、绝对下表); 而遇到女孩,则出栈(男孩相对下标--),输出女孩与男孩的绝对位置。 2014计算机学科夏令营上机考试 B:排队游戏 找规律……#¥%……

    2024年02月12日
    浏览(48)
  • 北京大学2016计算机学科夏令营上机考试

      目录 A:分段函数【水题】 B:单词翻转【暴力不水】 C:反反复复【字符串】 D:文件结构“图”【图】 E:Exchange Rates【这不是我能做的】 F:Dungeon Master【没看懂题目什么意思】 G:重建二叉树【树】   希望全出这种题哈哈哈哈哈哈哈 ①fgets这个输入方式比较特殊 ②正着输入,判断

    2024年02月12日
    浏览(61)
  • AI时代系列丛书(由北京大学出版社出版)

    在AI时代,程序员面临着新的机遇和挑战。为了适应这个快速发展的时代,掌握新技能并采取相应的应对策略是至关重要的。 对于办公人员或程序员来说,利用AI可以提高工作效率。例如,使用AI助手可以帮助自动化日常的重复性工作,如邮件筛选、日程安排等。此外,AI还可

    2024年02月03日
    浏览(52)
  • 集成电路工程实验——模拟部分(北京理工大学)

    在 CMOS 工艺下,设计一个 CMOS 运算放大器,并利用 Virtuoso 工具对其性能进行仿真和分析。 深入理解 CMOS 运算放大器的设计方法和性能分析方法。 设计符合下列要求的 CMOS 运算放大器,结构不限。 1、技术指标要求: 供电电压:VDD 3.3v GND 0v 输入信号:正弦差分信号 共模电压

    2024年02月08日
    浏览(80)
  • 北京理工大学操作系统复习——习题+知识点

    由于操作系统知识太多,再加上我总结的比较细,所以一篇放不下,拆分成了多篇文章。 操作系统笔记——概述、进程、并发控制 操作系统笔记——储存器管理、文件系统、设备管理 操作系统笔记——Linux系统实例分析、Windows系统实例分析 北理工操作系统实验合集 | API解读

    2024年02月03日
    浏览(55)
  • 北京大学 - 智元机器人(稚晖君)联合实验室正式成立

    北京大学计算机学院的官方公告宣布,现已正式成立了“北大 - 智元机器人联合实验室”。 智元机器人是由“华为天才少年”彭志辉(稚晖君)等来自多家大型科技公司的科技专业人才共同创立的,他们在2023年12月完成了一轮新的融资。 公告指出,“北大 - 智元机器人联合

    2024年02月03日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包