leetcode

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 };