推 sixB: 我好久沒寫扣了 哇啊啊啊啊啊 06/25 00:18
2106. Maximum Fruits Harvested After at Most K Steps
題目 :
給一個2-D array : fruits , fruits是以fruits[i][0]遞增排序
其中fruits[i][0]表示i水果的位置
fruits[i][1]表示i水果的數量
你的起始位置在startPos
可以任意變換行走的方向往右或往左
每當你到一個新的位置就可以得到該位置上所有的水果
你最多可以移動k步，請問最多可以拿到多少水果
思路 :
這題為sliding windows
假設要取得fruits[start]到fruits[end]這兩點間的水果
有分兩種走法
先往左再往右花費步數為 : fruits[end][0] + startPos - 2*fruits[start][0]
先往右再往走花費步數為 : 2*fruits[end][0] - startPos - fruits[start][0]
就先找出fruits中位置在[startPos-k, startPos+k]範圍內的點
接著從最左邊的點開始走
並且判斷上面兩種走法中的最小步數是否大於k
是的話就移動start，一直到小於k為止
就這樣一直紀錄最大獲得的水果數量
就能得到答案了
c++ code :
class Solution {
public:
int maxTotalFruits(vector<vector<int>> &fruits, int startPos, int k)
{
int start = 0, n = fruits.size(), sum = 0, ans = 0;
while (start < n && fruits[start][0] < startPos - k) {
start++;
}
for (int end = start; end < n && fruits[end][0] <= startPos + k; end++
) {
sum += fruits[end][1];
while (min(fruits[end][0] - 2 * fruits[start][0] + startPos,
2 * fruits[end][0] - fruits[start][0] - startPos) > k)
{
sum -= fruits[start][1];
start++;
}
ans = max(ans, sum);
}
return ans;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.121.235.241 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1750780574.A.67D.html