【題目敘述】https://zerojudge.tw/ShowProblem?problemid=b147
【解題想法】Greedy
- 讀入測資後，把每個花生田的植株的座標 (x, y) 及該植株下花生的数目 z 記錄下來。
- 座標為 one-based，因為「从路边跳到最靠近路边（即第一行）的某棵花生植株」也需要一單位時間。
- 接著以花生的数目進行排序，從數目多的植株開始判斷是否有足夠的時間採收。
- K 紀錄剩餘的時間。能否採收一株花生，要判斷時間是否足夠從目前位置 (x1, y1) 移動到新的位置 (x2, y2)，並進行採摘。
- 移動的時間 |x1 – x2| + |y1 – y2|
- 「采摘一棵植株下的花生」需要一單位時間。
- 還要保留足夠的時間 (x2)，從新的位置返回路邊。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define F first
#define S second
struct Node{
int x, y, z;
};
vector<Node> v;
bool cmp(Node a, Node b){
return a.z > b.z;
}
int main(){
int M, N, K, x;
while (cin >> M >> N >> K){
v.clear();
for (int i=1; i<=M; i++){
for (int j=1; j<=N; j++){
cin >> x;
if (x > 0) v.pb({i, j, x});
}
}
sort(v.begin(), v.end(), cmp);
int x = 0, y = 0;
int dis, ans = 0;
for (auto i: v){
if (x == 0) dis = i.x;
else dis = abs(i.x - x) + abs(i.y - y);
if (K - dis > i.x){
ans += i.z;
K = K - dis - 1;
x = i.x;
y = i.y;
//cout << "K = " << K << ", x = " << x << ", y = " << y << ", ans = " << ans << endl;
} else break;
}
cout << ans << '\n';
}
return 0;
}
Python code (credit: Amy Chou)
while True:
try:
M, N, K = map(int, input().split())
v = []
for i in range(M):
tmp = list(map(int, input().split()))
for j, z in enumerate(tmp):
if (z > 0):
v.append((z, i+1, j+1))
v.sort(key=lambda x: -x[0])
x = 0
y = 0
ans = 0
for z, nx, ny in v:
if (x == 0):
dis = nx
else:
dis = abs(nx - x) + abs(ny - y)
if (K - dis > nx):
K = K - dis - 1
ans += z
x = nx
y = ny
else:
break
print(ans)
print()
input()
except:
break