「一本通 1.1 练习 5」钓鱼

题目描述

$n$ 个湖排成一排，从湖 $1$ 出发只能向右走，总时间 $H$ 小时切成 $12H$ 个 5 分钟段；湖 $i$ 钓一段的产量首段为 $F_i$ 、每段递减 $D_i$ （负数按 0 计），从湖 $i$ 走到湖 $i+1$ 占 $T_i$ 段。选定终点湖后走路时间固定，其余时间自由分配给经过的湖钓鱼，求最多钓多少条鱼。

思路

枚举最远走到的湖 $L$ ，路程占用固定后，问题变成从各湖的逐段产量中取最大的 $k$ 段求和。所有湖的产量序列都是递减的，用一个大根堆每次弹出当前最大值、把该湖下一段产量入堆，贪心取满 $k$ 段即得该路线最优，取所有 $L$ 的最大值即可。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 09:58
# update_at: 2026-09-30 09:58

import sys
from heapq import heapify, heappop, heappush
from itertools import accumulate

SLOTS_PER_HOUR = 12  # 1 小时 = 60 分钟 = 12 个 5 分钟钓鱼段


def best_catch(first: list[int], dec: list[int], slots: int) -> int:
    """在 1..len(first) 号湖里钓满 slots 个 5 分钟段，最多能钓到多少条鱼。

    每湖"下一段的产量"以 (负产量, 衰减量) 入小根堆，弹堆顶即全局产量最高的湖：
    收下这一段后，该湖产量减自己的衰减量（下限 0）再回堆。各湖的产量序列都递减，
    依次取当前最大恰好取走合并后最大的 slots 项，就是最优的时间分配。
    """
    pool = [(-fish, drop) for fish, drop in zip(first, dec)]  # (负产量, 衰减量)
    heapify(pool)
    total = 0
    for _ in range(slots):
        neg, drop = heappop(pool)
        fish = -neg                       # 该湖这一段的产量
        total += fish
        heappush(pool, (-max(fish - drop, 0), drop))  # 同一湖下一段的产量
    return total


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    hours = next(data)
    first = [next(data) for _ in range(n)]     # 各湖第 1 个 5 分钟能钓到的鱼数
    dec = [next(data) for _ in range(n)]       # 每多钓一段比上一段减少的鱼数
    walk = [next(data) for _ in range(n - 1)]  # 湖 i→i+1 要花 5*T_i 分钟

    best = 0
    # 枚举最远走到哪个湖：一旦终点定了，路程时间就固定，剩下全部时间都能用来钓鱼
    for last, spent in enumerate(accumulate(walk, initial=0)):
        slots = SLOTS_PER_HOUR * hours - spent  # 剩余的 5 分钟钓鱼段数
        if slots <= 0:                          # 路程耗光了时间，更远的湖只会更亏
            break
        best = max(best, best_catch(first[:last + 1], dec, slots))
    print(best)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 23:30
 * update_at: 2026-10-05 23:30
 */
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 30;
const int SLOTS_PER_HOUR = 12; // 1 小时 = 12 个 5 分钟段

ll f[MAXN]; // 各湖第 1 个 5 分钟能钓到的鱼数
ll d[MAXN]; // 每多钓一段比上一段减少的鱼数
ll t[MAXN]; // 湖 i 到 i+1 的路程段数

// 在 1..m 号湖里钓满 slots 段，最多能钓到多少条鱼
ll best_catch(int m, int slots) {
    // 小根堆存 (负产量, 衰减量)，弹堆顶即当前产量最高的湖
    priority_queue<pair<ll, ll>, vector<pair<ll, ll> >, greater<pair<ll, ll> > > pq;
    for (int i = 1; i <= m; ++i) {
        pq.push(make_pair(-f[i], d[i]));
    }
    ll total = 0;
    for (int i = 0; i < slots; ++i) {
        pair<ll, ll> cur = pq.top();
        pq.pop();
        ll fish = -cur.first; // 该湖这一段的产量
        ll drop = cur.second; // 该湖的衰减量
        total += fish;
        ll nxt = fish - drop;
        if (nxt < 0) nxt = 0;
        pq.push(make_pair(-nxt, drop));
    }
    return total;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, H;
    if (!(cin >> n >> H)) return 0;
    for (int i = 1; i <= n; ++i) cin >> f[i];
    for (int i = 1; i <= n; ++i) cin >> d[i];
    for (int i = 1; i <= n - 1; ++i) cin >> t[i];

    ll best = 0;
    ll spent = 0; // 已走路程段数
    for (int L = 1; L <= n; ++L) {
        int slots = SLOTS_PER_HOUR * H - (int)spent;
        if (slots <= 0) break; // 路程耗光时间，更远的湖更亏
        best = max(best, best_catch(L, slots));
        spent += t[L];
    }
    cout << best << "\n";
    return 0;
}

「一本通 1.1 练习 5」钓鱼

目录

题目描述

思路

参考代码