目录
(一)题目网址+视频网址
(二)手写草稿思考
Part1: 慕课PPT
Part2: 笨蛋的学习
(一)题目网址+视频网址
北京大学网站在线算法题:1042 -- Gone Fishing (poj.org)
视频讲解(北京大学附郭炜教授) :程序设计与算法(二)算法基础_北京大学_中国大学MOOC(慕课) (icourse163.org)
(二)手写草稿思考
Part1: 慕课PPT
老师的视频讲解,发现老师好可爱的啊!居然去旅行的时候背着旅行包拍这种推广算法的视频!
Part2: 笨蛋的学习
说实话,我在看完老师的视频后,依旧对题意还没有非常理解,呜呜,救救我!
一个相关的大佬分析:(372条消息) 鱼塘钓鱼 贪心算法_小王不头秃的博客-CSDN博客
然后又仔细地研究了一下题目的意思+输入输出是个啥:
//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; // 程序结束
}
文章来源:https://www.toymoban.com/news/detail-449229.html
文章来源地址https://www.toymoban.com/news/detail-449229.html
到了这里,关于算法设计 || 第5题:钓鱼问题-北京大学网站在线算法题(贪心算法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!