信息学奥赛一本通T1431-钓鱼

解题思路:

该代码是一个贪心算法，用于解决在有限时间内从一系列湖泊中钓到尽可能多鱼的问题。它考虑了在每个湖泊停留的时间以及在湖泊之间移动所需的时间。

算法步骤：

初始化变量：

n: 湖泊的数量

h: 总时间（以分钟为单位）

fish[i]: 第 i 个湖泊的初始鱼数量

d[i]: 第 i 个湖泊的鱼每分钟减少的数量

t[i]: 从第 i 个湖泊走到第 i+1 个湖泊所需的时间（以分钟为单位）

walkTime: 从一个湖泊走到另一个湖泊所花费的时间

maxx: 迄今为止钓到的最大鱼数量

遍历每个湖泊：

计算剩余钓鱼时间 restTime。

初始化 res 为 0，表示在当前湖泊钓到的鱼数量。

创建一个优先队列 Q，其中元素为 (剩余鱼数量, 湖泊索引) 的 pair，并按剩余鱼数量从大到小排序。

将从第 1 个湖泊到第 i 个湖泊的鱼数量和湖泊索引放入优先队列。

在当前湖泊钓鱼：

只要剩余钓鱼时间大于 0 且优先队列不为空，就从优先队列中取出剩余鱼数量最多的湖泊。

将当前湖泊的剩余鱼数量添加到 res 中。

将当前湖泊的剩余鱼数量减少每分钟减少的数量。

如果当前湖泊还有剩余鱼，则将其重新放入优先队列。

更新最大鱼数量：

更新迄今为止钓到的最大鱼数量 maxx。

计算移动时间：

将从当前湖泊走到下一个湖泊所花费的时间添加到 walkTime 中。

输出结果：

输出 maxx，表示在给定时间内钓到的最大鱼数量。

注意事项:

参考代码:

#include <iostream>

#include <queue>

using namespace std;

int main() 

{

    int n, h;cin >> n >> h;

    h *= 60;

    int fish[n + 1],d[n + 1],t[n];

    for (int i = 1; i <= n; i++) cin >> fish[i];

    for (int i = 1; i <= n; i++) cin >> d[i];

    for (int i = 1; i <= n - 1; i++) cin >> t[i];

    int walkTime = 0;

    int maxx = -1;

    for (int i = 1; i <= n; i++) 

    {

        int restTime = h - walkTime;

        int res = 0;

        priority_queue<pair<int, int>> Q;

        for (int j = 1; j <= i; j++) //从只在一个地方钓鱼开始

        {

            Q.push(make_pair(fish[j], j));

        }

        while (restTime > 0 && !Q.empty()) {

            pair<int, int> temp = Q.top();

            Q.pop();

            res += temp.first;

            temp.first -= d[temp.second];

            if (temp.first > 0) {

                Q.push(temp);

            }

            restTime -= 5;

        }

        maxx = max(maxx, res);

        walkTime += t[i] * 5;

    }

    cout << maxx << endl;

    return 0;

}