前言

上篇：纯贪心做法
下篇：dp做法
题目：OJ1373

---

正题

有N个鱼塘，给出每分钟可以钓到的鱼数和每钓一次下一次钓减少的鱼数和到下一个鱼塘需要几分钟（不能回头）。求限定时间内最多能够钓到的鱼数

---

解题思路

由于是贪心优化，所以引用一下上篇的贪心

由于数据较小，我们枚举一下最后到达的池塘，然后在开始计算时间时就减去路程然后就可以在计算时不需要计算路程问题了。然后每次找最多鱼的池塘钓，然后减那个池塘的鱼数（这里讲一下原理，由于我们不能确定这时是继续钓好还是去下一个池塘钓好，于是我们就用这种方法确定每个池塘应该钓多久），以此类推直到时间耗尽，然后每次更新最大答案。

开一个大根堆，每次用堆来快速确定最大值。

---

代码

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct water{int fish,number;//记录鱼塘鱼数和编号 }; water a[101]; int tn,lt,num[101],t[101],mov[101],sum,n,m; void up(int x)//维护堆 {while (x>1 && a[x].fish>a[x/2].fish){swap(a[x],a[x/2]);x/=2;} } void down(int x)//维护堆 {int y;while (x*2<=tn && a[x].fish<a[x*2].fish || x*2+1<=tn && a[x].fish<a[x*2+1].fish){y=x*2;if (x*2+1<=tn && a[y].fish<a[y+1].fish) y++;swap(a[x],a[y]);x=y;} } int main() {scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&num[i]);for (int i=1;i<=n;i++) scanf("%d",&mov[i]);for (int i=1;i<n;i++) scanf("%d",&t[i]);scanf("%d",&m);for (int k=1;k<=n;k++){int time=m-lt,ans=0;tn=0;for (int i=1;i<=k;i++){a[++tn].fish=num[i];a[tn].number=i;//建堆up(tn);//维护}while (time>0 && a[1].fish>0)//时间耗尽或每鱼了{ans+=a[1].fish;//钓a[1].fish-=mov[a[1].number];//减去down(1);//维护堆time--;//消耗时间}sum=max(sum,ans);//h更新最大值lt+=t[k];//提前计算路程}printf("%d",sum); }

总结

以上是生活随笔为你收集整理的ssl2331OJ1373-鱼塘钓鱼 之2【贪心堆优化】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。