1373：鱼塘钓鱼(fishing）——优先队列+贪心

【题目描述】
有N个鱼塘排成一排（N<100），每个鱼塘中有一定数量的鱼，例如：N=5时，如下表：

即：在第1个鱼塘中钓鱼第1分钟内可钓到10条鱼，第2分钟内只能钓到8条鱼，……，第5分钟以后再也钓不到鱼了。从第1个鱼塘到第2个鱼塘需要3分钟，从第2个鱼塘到第3个鱼塘需要5分钟，……

给出一个截止时间T(T<1000)，设计一个钓鱼方案，从第1个鱼塘出发，希望能钓到最多的鱼。

假设能钓到鱼的数量仅和已钓鱼的次数有关，且每次钓鱼的时间都是整数分钟。

【输入】
共5行，分别表示：

第1行为N；

第2行为第1分钟各个鱼塘能钓到的鱼的数量，每个数据之间用一空格隔开；

第3行为每过1分钟各个鱼塘钓鱼数的减少量，每个数据之间用一空格隔开；

第4行为当前鱼塘到下一个相邻鱼塘需要的时间；

第5行为截止时间T。

【输出】
一个整数（不超过231−1），表示你的方案能钓到的最多的鱼。

【输入样例】
5
10 14 20 16 9
2 4 6 5 3
3 5 4 4
14
【输出样例】
76

分析

1. 此题是一道贪心+堆的题目，枚举每个池塘(从第一个开始)，然后减去到当前枚举到的池塘的走路的时间，然后看看他在0到i这i个池塘能钓多少鱼（每次都把0到i这些池塘的鱼放进堆里）；然后while循环，知道时间t用完以及池塘还有鱼，看看cnt的值和最终答案的值，选择大的；
2. 参考：第三部分 数据结构 – 第三章 树1373：鱼塘钓鱼(fishing），需注意 while (q.top().first && t)这样写是不行的，因为t可能会直接变为负数，然后还在循环内，也就是while循环只在等于0的条件下退出循环，正负数在里面都是死循环；

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> P;
const int N = 105;
priority_queue<P> q;
int a[N], b[N], c[N];
int n, T, ans, walk;

int main() {

    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];

    for (int i = 0; i < n; ++i)
        cin >> b[i];

    for (int i = 0; i < n - 1; ++i)
        cin >> c[i];
    cin >> T;
    //枚举每个池塘(从第一个开始)
    for (int i = 0; i < n; ++i) {
        //while (!q.empty())q.pop();
        int t = T - walk;//减去走路的时间
        //从第一个池塘开始，到当前所枚举到的池塘
        for (int j = 0; j <= i; ++j)
            q.push(make_pair(a[j], j));
        int cnt = 0;
        while (q.top().first > 0 && t > 0) {
            //时间没用完+当前池塘还不空
            P temp = q.top();
            q.pop();
            cnt += temp.first;
            //q.top().first-=b[i];不能直接修改，所以用一个temp修改
            temp.first -= b[temp.second];
            q.push(temp);
            t--;
        }
        walk += c[i];
        ans = max(ans, cnt);
    }
    cout << ans;
    return 0;
}