1014 added.

liuyubobobo · liuyubobobo · commit ecd739c896e8 · 2019-03-16T22:10:25.000-07:00
diff --git a/1014-Capacity-To-Ship-Packages-Within-D-Days/cpp-1014/CMakeLists.txt b/1014-Capacity-To-Ship-Packages-Within-D-Days/cpp-1014/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.13)
+project(C)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(C main.cpp)
diff --git a/1014-Capacity-To-Ship-Packages-Within-D-Days/cpp-1014/main.cpp b/1014-Capacity-To-Ship-Packages-Within-D-Days/cpp-1014/main.cpp
@@ -0,0 +1,56 @@
+/// Source : https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/
+/// Author : liuyubobobo
+/// Time   : 2019-03-16
+
+#include <iostream>
+#include <vector>
+#include <numeric>
+
+using namespace std;
+
+
+/// Binary Search
+/// Time Complexity: O(nlog(sum(weights)))
+/// Space Complexity: O(1)
+class Solution {
+public:
+    int shipWithinDays(vector<int>& weights, int D) {
+
+        int l = *max_element(weights.begin(), weights.end()),
+            r = accumulate(weights.begin(), weights.end(), 0);
+        while(l < r){
+//            cout << "check " << l << " " << r <<  endl;
+            int mid = (l + r) / 2;
+            if(ok(weights, mid, D))
+                r = mid;
+            else
+                l = mid + 1;
+        }
+        return l;
+    }
+
+private:
+    bool ok(const vector<int>& weights, int C, int D){
+
+        int d = 0, cur = 0;
+        for(int w: weights)
+            if(cur + w <= C) cur += w;
+            else d ++, cur = w;
+        if(cur) d ++;
+        return d <= D;
+    }
+};
+
+
+int main() {
+
+    vector<int> weight1 = {1,2,3,4,5,6,7,8,9,10};
+    cout << Solution().shipWithinDays(weight1, 5) << endl;
+    // 15
+
+    vector<int> weight2 = {1,2,3,1,1};
+    cout << Solution().shipWithinDays(weight2, 4) << endl;
+    // 3
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -681,4 +681,5 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | | | | | | |
 | 1012 | [Complement of Base 10 Integer](https://leetcode.com/problems/complement-of-base-10-integer/) | [无] | [C++](1012-Complement-of-Base-10-Integer/cpp-1012/) | | |
 | 1013 | [Pairs of Songs With Total Durations Divisible by 60](https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/) | [无] | [C++](1013-Pairs-of-Songs-With-Total-Durations-Divisible-by-60/cpp-1013/) | | |
+| 1014 | [Capacity To Ship Packages Within D Days](https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/) | [无] | [C++](1014-Capacity-To-Ship-Packages-Within-D-Days/cpp-1014/) | | |
 | | | | | | |
