SHARE
TWEET

Untitled

a guest May 21st, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int splitArray(vector<int>& nums, int m) {
  4.         long long lo = 0;
  5.         long long hi = accumulate(nums.begin(), nums.end(), 0ll);
  6.  
  7.         while (hi - lo > 1) {
  8.             auto mid = lo + (hi - lo) / 2;
  9.             if (CanSplit(nums, m, mid)) hi = mid;
  10.             else lo = mid;
  11.         }
  12.        
  13.         return hi;
  14.     }
  15. private:
  16.     bool CanSplit(const vector<int>& nums, int m, long long max_sum) {
  17.         int curr_chunk_id = 1;
  18.         long long curr_sum = 0;
  19.        
  20.         for (int i = 0; i < nums.size(); ++i) {
  21.             if (nums[i] > max_sum) return false;
  22.             if (curr_sum + nums[i] <= max_sum) {
  23.                 curr_sum += nums[i];
  24.             } else {
  25.                 ++curr_chunk_id;
  26.                 curr_sum = nums[i];
  27.             }
  28.         }
  29.        
  30.         return curr_chunk_id <= m;
  31.     }
  32. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top