Create 2106.Maximum-Fruits-Harvested-After-at-Most-K-Steps_v2.cpp

wisdompeak · web-flow · commit 238e118fcabb · 2021-12-19T22:40:54.000-08:00
diff --git a/Binary_Search/2106.Maximum-Fruits-Harvested-After-at-Most-K-Steps/2106.Maximum-Fruits-Harvested-After-at-Most-K-Steps_v2.cpp b/Binary_Search/2106.Maximum-Fruits-Harvested-After-at-Most-K-Steps/2106.Maximum-Fruits-Harvested-After-at-Most-K-Steps_v2.cpp
@@ -0,0 +1,36 @@
+class Solution {
+public:
+    int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) 
+    {
+        int n = fruits.size();
+        vector<int>pos(n);
+        vector<int>presum(n);
+        for (int i=0; i<n; i++)
+        {
+            pos[i] = fruits[i][0];
+            presum[i] = (i==0?0:presum[i-1]) + fruits[i][1];
+        }
+        
+        int ret = 0;
+        for (int i=0; i<n; i++)
+        {
+            if (pos[i]<=startPos)
+            {
+                double d = k - (startPos-pos[i]);
+                if (d<0) continue;
+                int j = upper_bound(pos.begin(), pos.end(), startPos+d/2) - pos.begin() - 1;
+                if (j>=0 && j<n)
+                    ret = max(ret, presum[j] - (i==0?0:presum[i-1]));
+            }
+            else
+            {
+                double d = k - (pos[i]-startPos);
+                if (d<0) continue;   
+                int j = lower_bound(pos.begin(), pos.end(), startPos-d/2) - pos.begin();
+                if (j>=0 && j<n)
+                    ret = max(ret, presum[i]- (j==0?0:presum[j-1]));
+            }
+        }
+        return ret;
+    }
+};
