Optimal Fishing Strategy: A Greedy Algorithm Approach
Optimal Fishing Strategy: A Greedy Algorithm Approach
Problem Description
There are n fishing lakes arranged horizontally along a road, numbered 1 to n from left to right. A person has H hours of free time and wants to catch as many fish as possible. They start at lake 1 and move right, choosing to spend time (in multiples of 5 minutes) at certain lakes to fish. They finish at some lake. The time to move from lake i to lake i+1 is 5×Ti minutes. When staying at lake i, the first 5 minutes yields Fi fish, and each subsequent 5-minute interval yields Di fewer fish than the previous one. If the reduced amount is negative, it becomes zero. The task is to determine the maximum number of fish that can be caught.
Input
- First line: integer n (number of lakes)
- Second line: integer H (free time in hours)
- Third line: n integers representing the number of fish caught in the first 5 minutes at each lake
- Fourth line: n integers representing the reduction in fish caught every 5 minutes at each lake
- Fifth line: n-1 integers representing Ti for traveling from lake i to lake i+1
Output
A single line with the maximum number of fish that can be caught.
Sample Input
3
1
4 5 6
1 2 1
1 2
Sample Output
35
Sample Explanation
- 15 minutes at lake 1: 4+3+2=9 fish
- 10 minutes at lake 2: 5+3=8 fish
- 20 minutes at lake 3: 6+5+4+3=18 fish
- Travel time between lakes: 15 minutes
- Total: 35 fish (maximum possible)
Solution Approach
We enumerate the number of lakes to consider (from 1 to n). For each case, we:
- Subtract the travel time to reach those lakes
- Use a priority queue to select the lake that gives the most fish in the next 5-minute interval
- Update the fish count for that lake and repeat until time runs out
- Track the maximum fish count across all scenarios
Code Implementation
#include
#include
#include
#include
using namespace std;
// Structure to represent fishing lakes
struct Lake {
int initial_fish; // Fish caught in first 5 minutes
int reduction; // Reduction in fish every 5 minutes
int current_fish; // Current fish count for next 5 minutes
// Overload < operator for priority queue
bool operator<(const Lake& other) const {
return current_fish < other.current_fish;
}
};
int main() {
int n, H;
cin >> n >> H;
int total_time = H * 60; // Convert hours to minutes
vector initial_fish(n);
vector reduction(n);
vector travel_time(n-1);
// Read input values
for (int i = 0; i < n; i++) {
cin >> initial_fish[i];
}
for (int i = 0; i < n; i++) {
cin >> reduction[i];
}
for (int i = 0; i < n-1; i++) {
cin >> travel_time[i];
}
int max_fish = 0;
// Try all possible numbers of lakes to visit (from 1 to n)
for (int num_lakes = 1; num_lakes <= n; num_lakes++) {
int remaining_time = total_time;
// Subtract travel time to reach these lakes
for (int i = 0; i < num_lakes - 1; i++) {
remaining_time -= travel_time[i] * 5;
}
// If no time left after traveling, skip
if (remaining_time <= 0) continue;
// Create priority queue with current lakes
priority_queue lakes;
for (int i = 0; i < num_lakes; i++) {
Lake lake;
lake.initial_fish = initial_fish[i];
lake.reduction = reduction[i];
lake.current_fish = initial_fish[i];
lakes.push(lake);
}
int current_fish_count = 0;
// Fish in 5-minute intervals until time runs out
while (remaining_time >= 5) {
if (lakes.empty()) break;
Lake best_lake = lakes.top();
lakes.pop();
current_fish_count += best_lake.current_fish;
remaining_time -= 5;
// Update the lake's fish count for next interval
best_lake.current_fish -= best_lake.reduction;
if (best_lake.current_fish > 0) {
lakes.push(best_lake);
}
}
// Update maximum fish count
max_fish = max(max_fish, current_fish_count);
}
cout << max_fish << endl;
return 0;
}
