1 条题解
-
0
解析:
依次枚举在前i个湖中钓鱼的情况;
先减掉路上消耗的时间;
选这i个湖中5分钟可以钓最多的鱼的湖钓5分钟,然后更新这个湖5分钟可以钓鱼的数量;
直到时间消耗光;
使用优先队列维护可钓鱼的湖;
#include<bits/stdc++.h> using namespace std; int H,n; int t;//分钟数 int a[105];//a[i]表示第i个湖第1个5分钟可以钓到鱼的数量 int d[105];//d[i]表示第i个湖每5分钟钓鱼的减少数量 int T[105];//T[i]表示从第i个湖到第i+1个湖所用的时间为5*T[i] struct node{ int a;//当前5分钟可以钓鱼数量 int d;//每5分钟减少数量 //重置小于号运算符,钓鱼数量小的小 bool operator < (const node &x) const{ return a<x.a; } }; priority_queue <node> q;//大根堆 int ans=0; int main() { cin>>n>>H; t=H*60; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ cin>>d[i]; } for(int i=1;i<n;i++){ cin>>T[i]; } for(int i=1;i<=n;i++){//枚举钓鱼的湖的数量 int t1=t;//时间 for(int j=1;j<i;j++){//去掉走路用的时间 t1-=T[j]*5; } while(!q.empty()){//清空优先队列 q.pop(); } for(int j=1;j<=i;j++){//枚举每个鱼塘 node x; x.a=a[j];//当前鱼塘5分钟可以钓鱼数量 x.d=d[j];//每5分钟减少数量 q.push(x); } int sum=0;//钓鱼数量 while (t1>=5){//只要时间大于等于5分钟,就可以钓鱼 if (!q.empty()){//还有鱼塘可以钓到鱼 node x=q.top();//捡最多的钓 sum+=x.a;//钓鱼数量 t1-=5;//消耗5分钟 q.pop();//钓完弹出 x.a-=x.d;//计算这个鱼塘下五分钟可以钓鱼数量 if (x.a>0){//如果数量大于0 q.push(x);//加入优先队列 } }else{//如果没有能钓到鱼的鱼塘,退出循环 break; } } ans=max(ans,sum);//取最大值 } cout<<ans; return 0; }
- 1
信息
- ID
- 605
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者