解題觀念
Greedy + STL
可以參考我的課程簡報：Greedy & Graph
題目敘述
John 想花 h 小時去 n 個湖泊釣魚(湖泊由左至右編號1, 2, 3….n)
他希望先安排行程,讓本次釣魚行程有最大的漁獲量
他規劃從湖泊 1 開始,可以選擇花費時間釣魚或是直接去湖泊 2
如果過了一個湖泊就不能回頭
而每個湖泊前 5 分鐘可釣到 f 隻魚,而每釣 5 分鐘釣魚量會減少 d 隻
另會給予湖泊 I 與湖泊 i+1 間的交通時間 ti (為 5 分鐘的倍數)
請設計一個可有最大漁獲量的行程
如果不只一個最大漁獲量行程,則輸出從湖泊 1 釣魚時間 ~ 湖泊 n 釣魚
時間中字典序最大的一組行程
每組輸入中
第一行為數字 n,代表有多少湖泊(湖泊由左至右編號1, 2…n)
第二行為數字 h,為 John 欲花費的釣魚時間(單位為小時)
第三行根據 n 的數量讀取 f,依序表示在第 i 個湖泊前 5 分鐘的釣魚量
第四行根據 n 的數量讀取 d,依序表示第 i 個湖泊每隔 5 分鐘減少的釣魚量
第五行根據 n-1 的數量讀取 ti,依序表示第 i 到第 i+1 個湖泊的交通時間(單
位為 5 分鐘)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 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
|
Output
每組輸出中
第一行為每個湖泊釣魚時間,
每個湖泊的時間之間用 “,” 和一個空白隔開
最後一個湖泊後沒有 “,” 和任何空白
第二行輸出文字:”Number of fish expected: “
和最大漁獲量,中間用一個空白隔開
每組輸出之間需相隔一行
1
2
3
4
5
6
7
8
| 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
|
解題觀念簡報參考
STL - Priority Queue
Greedy
Solution Code
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| #include<bits/stdc++.h>
using namespace std;
struct Fishing{
int fish;
int dec;
int idx;
bool operator < (const Fishing &rhs) const{
if(fish == rhs.fish) return idx > rhs.idx;
return fish < rhs.fish;
}
}fishing[25+5];
int main(){
int n;
bool space = false;
while(cin >> n && n){
if(space) cout << endl;
space = true;
int time;
cin >> time;
time *= 60/5;
int fish[25+5], dec[25+5];
for(int i = 0; i < n; ++i){
cin >> fish[i];
}
for(int i = 0; i < n; ++i){
cin >> dec[i];
}
int trafficTime[25+5];
trafficTime[0] = 0;
for(int i = 1; i < n; ++i){
cin >> trafficTime[i];
}
int maxi = -1;
int ans[25+5];
for(int i = 0; i < n; ++i){
priority_queue<Fishing> pq;
int tmpTime = time;
for(int j = 0; j <= i; ++j){
tmpTime -= trafficTime[j];
if(fish[j] == 0) continue;
pq.push({fish[j], dec[j], j});
}
int tmpTotal = 0, tmpLake[25+5];
memset(tmpLake, 0, sizeof(tmpLake));
while(tmpTime > 0 && !pq.empty()){
Fishing now = pq.top();
pq.pop();
tmpTotal += now.fish;
tmpLake[now.idx] += 5;
tmpTime -= 1;
if(now.fish - now.dec <= 0) continue;
pq.push({now.fish - now.dec, now.dec, now.idx});
}
if(tmpTime > 0) tmpLake[0] += (tmpTime * 5);
if(tmpTotal > maxi){
for(int j = 0; j < n; ++j) ans[j] = tmpLake[j];
maxi = tmpTotal;
}
}
cout << ans[0];
for(int i = 1; i < n; ++i){
cout << ", " << ans[i];
}
cout << endl << "Number of fish expected: " << maxi << endl;
}
}
|
