01042: Gone Fishing
greedy, http://cs101.openjudge.cn/practice/01042/
John is going on a fishing trip. He has h hours available (1 <= h <= 16), and there are n lakes in the area (2 <= n <= 25) all reachable along a single, one-way road. John starts at lake 1, but he can finish at any lake he wants. He can only travel from one lake to the next one, but he does not have to stop at any lake unless he wishes to. For each i = 1,...,n - 1, the number of 5-minute intervals it takes to travel from lake i to lake i + 1 is denoted ti (0 < ti <=192). For example, t3 = 4 means that it takes 20 minutes to travel from lake 3 to lake 4. To help plan his fishing trip, John has gathered some information about the lakes. For each lake i, the number of fish expected to be caught in the initial 5 minutes, denoted fi( fi >= 0 ), is known. Each 5 minutes of fishing decreases the number of fish expected to be caught in the next 5-minute interval by a constant rate of di (di >= 0). If the number of fish expected to be caught in an interval is less than or equal to di , there will be no more fish left in the lake in the next interval. To simplify the planning, John assumes that no one else will be fishing at the lakes to affect the number of fish he expects to catch. Write a program to help John plan his fishing trip to maximize the number of fish expected to be caught. The number of minutes spent at each lake must be a multiple of 5.
输入
You will be given a number of cases in the input. Each case starts with a line containing n. This is followed by a line containing h. Next, there is a line of n integers specifying fi (1 <= i <=n), then a line of n integers di (1 <=i <=n), and finally, a line of n - 1 integers ti (1 <=i <=n - 1). Input is terminated by a case in which n = 0.
输出
For each test case, print the number of minutes spent at each lake, separated by commas, for the plan achieving the maximum number of fish expected to be caught (you should print the entire plan on one line even if it exceeds 80 characters). This is followed by a line containing the number of fish expected. If multiple plans exist, choose the one that spends as long as possible at lake 1, even if no fish are expected to be caught in some intervals. If there is still a tie, choose the one that spends as long as possible at lake 2, and so on. Insert a blank line between cases.
样例输入
2
1
10 1
2 5
2
4
4
10 15 20 17
0 3 4 3
1 2 3
4
4
10 15 50 30
0 3 4 3
1 2 3
0样例输出
45, 5
Number of fish expected: 31
240, 0, 0, 0
Number of fish expected: 480
115, 10, 50, 35
Number of fish expected: 724来源: East Central North America 1999
# 蒋子轩23工学院
from heapq import heappush, heappop
while True:
n = int(input())
if n == 0:
break
h = int(input()) * 12
ans = -1 #最大钓鱼数量
res = [0] * n #每个湖上所花费的时间
f = list(map(int, input().split()))
d = list(map(int, input().split()))
t = [0] + (list(map(int, input().split())) if n > 1 else [])
#枚举第几个湖泊结束
#对于每种情况贪心算法，它在每个湖上都试图钓尽可能多的鱼，并始终优先考虑鱼的数量多的湖。
for i in range(n):
now = 0 #该情况钓鱼数量
q = [] #优先队列
lakes = [{'id': j, 'f': f[j], 'd': d[j]} for j in range(i + 1)]
for lake in lakes:
# 使得鱼的数量多的湖排在优先队列的前面（取负实现）。如果鱼的数量相同，那么ID小的湖会排在前面。
heappush(q, (-lake['f'], lake['id']))
tmp = [0] * n #该情况每个湖钓鱼时间
time_left = h - sum(t[:i + 1]) #湖上剩余的时间
while time_left > 0:
fish_count, idx = heappop(q)
fish_count = -fish_count #变回正数
tmp[idx] += 1
now += fish_count
lakes[idx]['f'] -= lakes[idx]['d']
if lakes[idx]['f'] < 0:
lakes[idx]['f'] = 0
heappush(q, (-lakes[idx]['f'], idx))
time_left -= 1
if now > ans:
ans = now
res = tmp.copy()
print(", ".join(str(val * 5) for val in res))
print("Number of fish expected:", ans)
print()一步步分析题意与算法逻辑，并在保留思路的同时优化与精炼。
🧩 一、题目逻辑核心
John 有：
( n ) 个湖；
( h ) 小时（即 ( h × 12 ) 个 5 分钟单位）；
每个湖初始鱼数 ( f_i )，每 5 分钟鱼量减少 ( d_i )；
相邻湖间旅行时间 ( t_i )（以 5 分钟为单位）；
可以在任意一个湖结束，不必到达最后一个。
目标：
规划每个湖的钓鱼时间，使总捕获量最大。若有多种方案，选前面湖停得久的方案。
🧮 二、思路分析（贪心 + 枚举）
枚举终点湖
i（意味着他会钓到第 i 个湖为止）。用去的旅行时间：
sum(t[:i+1])可用时间：
time_left = h - sum(t[:i+1])
在前 i+1 个湖中钓鱼（按优先队列贪心）：
每次挑鱼最多的湖钓一次；
钓完更新该湖鱼数；
重复直到时间用完。
记录：
总鱼量
now每个湖钓鱼次数
tmp若总鱼量更大或（同鱼量但更靠前湖时间更长）→ 更新答案。
💡 三、关键贪心细节
在每个时间步：
选择当前
f[i]最大的湖；若相同，选择编号最小（靠前的湖）；
每次钓鱼后减少
f[i] -= d[i]，最低为 0；用堆（负值排序）保证
O(log n)的最高鱼量获取。
⚙️ 四、原代码分析与优化点
你的版本功能正确，以下几点可优化：
| 优化点 | 原代码问题 | 优化方式 |
|---|---|---|
| 可读性 | 混用 dict 与列表 | 直接用列表存鱼量即可 |
| 拷贝 | 每次都新建 dict list | 用 fcopy = f[:i+1] 更快 |
| 重复逻辑 | heappush/pop 重复负号处理 | 用 (-f, i) 统一表示 |
| 代码结构 | 多处嵌套 | 可抽取为函数 |
✅ 五、优化后完整代码
from heapq import heappush, heappop
while True:
n = int(input())
if n == 0:
break
h = int(input()) * 12 # 转为5分钟单位
f = list(map(int, input().split()))
d = list(map(int, input().split()))
t = [0] + (list(map(int, input().split())) if n > 1 else [])
best_fish = -1
best_plan = [0] * n
# 枚举终止湖 i
for i in range(n):
travel = sum(t[:i + 1])
if travel > h:
break # 时间不够到这个湖
time_left = h - travel
cur_f = f[:i + 1] # 当前鱼量
time_plan = [0] * n
total_fish = 0
# 构建优先队列 (-fish, idx)
pq = [(-cur_f[j], j) for j in range(i + 1)]
heap = pq[:]
import heapq
heapq.heapify(heap)
while time_left > 0:
fish, idx = heappop(heap)
fish = -fish
total_fish += fish
time_plan[idx] += 1
# 鱼减少
cur_f[idx] = max(0, cur_f[idx] - d[idx])
heappush(heap, (-cur_f[idx], idx))
time_left -= 1
# 比较更新最优解（先比较鱼数，再比较时间字典序）
if total_fish > best_fish or (total_fish == best_fish and time_plan > best_plan):
best_fish = total_fish
best_plan = time_plan[:]
print(", ".join(str(x * 5) for x in best_plan))
print("Number of fish expected:", best_fish)
print()六、性能与正确性说明
| 指标 | 分析 |
|---|---|
| 时间复杂度 | O(n² × h) 但 n ≤ 25, h ≤ 16×12=192，因此可接受 |
| 空间复杂度 | O(n) |
| 多解判定 | 用字典序比较 time_plan > best_plan 实现“前湖优先”规则 |
| 输出格式 | 每湖分钟数用逗号隔开、再输出总鱼量 |