钓鱼

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1315 字
枚举终点湖，剩余时间用堆贪心分配
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1431
// 题意：n 个湖从左到右排列，有 H 小时，在第 i 个湖每 5 分钟钓到的鱼递减 D_i，走路耗时按 5 分钟为单位给出，求最多能钓多少鱼。
// 思路：枚举最远走到第 k 个湖，剩下的时间用优先队列在 1..k 号湖之间贪心分配。
// 1. 总时间按 5 分钟折算成 H * 12 个单位，走路只花在 1..k 之间的路程上。
// 2. 每个单位时间取当前产量最高的湖钓一次，产量下降后重新入堆。
// 3. 对所有 k 取最大值。
// 复杂度：O(n^2 log n) 时间 / O(n) 空间
// 易错点：时间是 5 分钟一个单位，H 小时要先乘 12，路程 T_i 本身就是单位数，不用再乘 5。
// 易错点：产量减到 0 之后继续钓也只得 0，但为了统一处理仍要把 0 入堆（或剩余时间直接跳过）。
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, H;
    if(!(cin >> n)) return 0;
    if(!(cin >> H)) return 0;
    vector<int> f(n), d(n), t(n);
    for(int i = 0; i < n; i++) cin >> f[i];
    for(int i = 0; i < n; i++) cin >> d[i];
    for(int i = 0; i + 1 < n; i++) cin >> t[i];
    int total = H * 12;
    int best = 0;
    for(int k = 1; k <= n; k++){
        int time = total;
        for(int i = 0; i + 1 < k; i++) time -= t[i];
        if(time < 0) break;
        priority_queue<pair<int, int>> pq;
        for(int i = 0; i < k; i++) pq.push({f[i], i});
        int sum = 0;
        for(int s = 0; s < time; s++){
            auto cur = pq.top();
            pq.pop();
            if(cur.first <= 0) break;
            sum += cur.first;
            pq.push({cur.first - d[cur.second], cur.second});
        }
        best = max(best, sum);
    }
    cout << best << "\n";
    return 0;
}
钓鱼

正文

一本通·提高篇的其它内容
