Array Division
You are given an array of \(n\) positive integers. Divide the array into \(k\) subarrays (contiguous parts) so that the maximum sum of a subarray is as small as possible.
Constraints:
- \(1 \le n \le 2 \cdot 10^5\)
- \(1 \le k \le n\)
- \(1 \le x_i \le 10^9\)
Input:
- First line: two integers \(n\) and \(k\).
- Second line: \(n\) integers \(x_1, x_2, \dots, x_n\).
Output:
- One integer — the maximum sum of a subarray in an optimal division.
Example:
Input:
5 3
2 4 7 3 5
Output:
8
(An optimal division is \([2, 4]\), \([7]\), \([3, 5]\), with sums \(6\), \(7\), and \(8\).)
Solution
We use binary search on the answer, as in Factory Machines.
Fix a limit \(L\) and ask: can we divide the array into at most \(k\) subarrays so that every sum is at most \(L\)? If this is possible for \(L\), it is also possible for every larger limit, so the binary search finds the smallest possible \(L\). A division into fewer than \(k\) subarrays can always be split further into exactly \(k\) subarrays, because every element is a subarray on its own and \(k \le n\).
To check a limit \(L\), we use a greedy method: go from left to right and add each element to the current subarray while the sum stays at most \(L\). When the next element does not fit, start a new subarray with it. Making each subarray as long as possible never increases the number of subarrays, so the limit is possible exactly when the greedy method uses at most \(k\) subarrays.
The range of the search:
- The answer is at least the largest element, because that element is in some subarray. This also guarantees that every element fits into a subarray on its own.
- The answer is at most the sum of all elements (one subarray).
Each check takes \(O(n)\) time, so the whole solution takes \(O(n \log (\sum x_i))\) time.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, k;
vector<long long> x;
// can the array be divided into at most k subarrays with sums at most limit?
// limit is never smaller than the largest element
bool possible(long long limit) {
int subarrays = 1;
long long sum = 0;
for (int i = 0; i < n; i++) {
if (sum + x[i] > limit) {
subarrays++; // start a new subarray at x[i]
sum = 0;
}
sum += x[i];
}
return subarrays <= k;
}
int main() {
cin >> n >> k;
x.resize(n);
long long largest = 0, total = 0;
for (int i = 0; i < n; i++) {
cin >> x[i];
largest = max(largest, x[i]);
total += x[i];
}
long long left = largest, right = total;
long long answer = total;
while (left <= right) {
long long mid = (left + right) / 2;
if (possible(mid)) {
answer = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
cout << answer << "\n";
}- The sum of all elements reaches \(2 \cdot 10^{14}\), so use
long longfor the sums and the limits.