leetcode/problems-cpp/split-array-largest-sum/solution.h at main · goodstudyqaq/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/*
Code generated by https://github.com/goodstudyqaq/leetcode-local-tester
*/
#if __has_include("../utils/cpp/help.hpp")
#include "../utils/cpp/help.hpp"
#elif __has_include("../../utils/cpp/help.hpp")
#include "../../utils/cpp/help.hpp"
#else
#define debug(...) 42
#endif

class Solution {
   public:
    int splitArray(vector<int>& nums, int k) {
        int n = nums.size();

        vector<int> sum(n + 1);
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }

        int l = 0, r = sum[n];
        int ans = -1;

        auto check = [&](int val) {
            int now = 0;
            int need = 0;
            while (now < n) {
                if (need == k) return false;
                int go = now;
                int x = 0;
                while (go < n && x + nums[go] <= val) {
                    x += nums[go];
                    go++;
                }
                need++;
                now = go;
            }
            return true;
        };

        while (l <= r) {
            int mid = l + r >> 1;
            if (check(mid)) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return ans;
;

    }
};