leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0410.cpp (830B)

0 class Solution { 1 int res = INT_MAX; 2 3 bool doable(const vector<int> &nums, int cuts, long long maxi) { 4 long long acc = 0; 5 6 for (const int num : nums) { 7 if (acc + num <= maxi) 8 acc += num; 9 else { 10 if (--cuts < 0) return false; 11 acc = num; 12 } 13 } 14 15 return true; 16 } 17 18 public: 19 int splitArray(const vector<int> &nums, int k) { 20 long long low = 0, high = 0; 21 22 for (const long long n : nums) { 23 low = max(low, n); 24 high += n; 25 } 26 27 while (low < high) { 28 const auto mid = low + (high - low) / 2; 29 if (doable(nums, k - 1, mid)) 30 high = mid; 31 else 32 low = mid + 1; 33 } 34 35 return low; 36 } 37 };