算法:枚举,贪心
这道题我们枚举最后走到哪个鱼塘for (int k = 1; k <= n; k++)
。这就意味着,前面k个鱼塘我们都走过了(后面的鱼塘暂时不管,这里是枚举终点),所以前面k个鱼塘赶路的时间用前缀和T[i]
处理即可
所以每循环一次k,前k个鱼塘就都走到了,那么除去你走路的时间,剩下钓鱼的时间就是fish_time = Time - T[k]
。剩下的时间全部用来钓鱼(走路的时间已经去掉了),所以用大根堆来维护当前哪个池塘能钓最多的鱼
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int n;
int num[N], d[N], T[N]; // num:第一分钟能钓到的鱼,d:每分钟减少的数量,T:走到下一个需要的时间
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> num[i];
for (int i = 1; i <= n; i++) cin >> d[i];
// 默认走到第一个鱼塘的时间是0,所以前缀和从2开始算
for (int i = 2; i <= n; i++)
{
cin >> T[i];
T[i] += T[i - 1];
}
int Time;
cin >> Time;
int ans = -1;
// 只在前k个鱼塘钓鱼
for (int k = 1; k <= n; k++)
{
int fish_time = Time - T[k]; // 除去鱼塘之间赶路的时间,剩下的钓鱼的时间
priority_queue<PII> q; // 用大根堆维护当前能钓的最多的鱼
for (int i = 1; i <= k; i++)
q.push({num[i], i}); // 前k个鱼塘的鱼的数量的大根堆, 后面跟一个下标方便后续的计算
int fish = 0; // 前k个鱼塘能钓到的鱼
while (q.size() && fish_time > 0) // 要有鱼可以钓,并且有时间钓鱼才循环
{
PII t = q.top();
q.pop();
int var = t.y;
fish += t.x;
fish_time--; // 钓鱼时间减1
t.x -= d[var]; // 钓完鱼之后,根据题意减去部分鱼
if (t.x > 0) q.push({t.x, var}); // 如果池塘钓不到鱼了,也就不需要入队了
}
ans = max(ans, fish);
}
cout << ans << endl;
return 0;
}
我的理解是选择哪个池塘钓鱼和池塘的顺序没有关系,每次都选择有最多的鱼的池塘,在最后可以将对应的选择按顺序进行,所以只需要求出最优解,不用考虑按顺序迁移池塘。
学长好厉害
有一个问题,对于每次枚举钓过鱼塘数目,先钓鱼数目多的鱼塘,鱼塘数目排序了,可是鱼塘之间路程时间没有排序,是我理解错了吗,我不太懂为什么这样输出是对的
因为他用了优先队列,大根堆啊
大根堆里不是只有鱼塘数目和下标吗,没有时间诶
走路的时间已经在 int fish_time = Time - T[k]; 这行代码中减去了。然后代码的意思不是说哪个池塘能钓最多的鱼我就马上去哪个池塘,这样子的话赶路时间就会重复了。这个代码更像是提供了一个方案,减去赶路时间后,我在前面的这些鱼塘中,通过计算后每个鱼塘我要钓多少次鱼。换成这个思路应该就好理解了。
这么一说就明白了,报意思,没有认真看文章
是不是可以举个极端例子来帮助理解,就是比如我到某一个非常远的池塘,尽管池塘里有很多鱼,但是时间减去抵达鱼塘的时间为负数,所以抵达鱼塘的时间在代码里先减掉,再贪心怎样钓到最多的鱼
简短有力
%%%
哥们你真是天才
天才
orz
简单易懂,STL好评
言简意赅
解释我拿啦
写得太好啦