【入门】分割数组的最大值
题目描述
给定一个非负整数数组 和一个整数 ，你需要将这个数组分成 个非空的连续子数组。
设计一个算法使得这 个子数组各自和的 最大值最小。
- 提示：这是第 1 类二分问题的模板，不熟悉的同学可以参考：
老师的模板
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
// 高级语法: 可以理解为申明一个函数 bool ok(int tmp) { }
auto ok = [&](int mid) -> bool {
int d = 0; // 和不超过 mid 的条件下的分割段数
for (int i = 0; i < n; i++) {
if (a[i] > mid) return false; // a[i] > mid 直接不行
// 在和不超过 tmp 的前提下，每个子段都贪心地选择尽可能多的数
int sum = a[i];
while (i + 1 < n && sum + a[i + 1] <= mid) sum += a[++i];
d++;
}
// 如果分割出来的子段个数不超过 k, 那么 mid 就可行
return d <= k;
};
// 二分枚举答案, 这里求最大值最小, 注意边界
// 确定边界, l = 0, r 最大为数组的和
// accumulate(): 把 a.beign() 到 a.end() 的和累加到 0, 就是求和
int l = 0, r = accumulate(a.begin(), a.end(), 0);
while (l != r) {
int mid = (l + r) / 2; // 注意：第 1 类二分, 这里没有 +1
if (ok(mid)) r = mid; // mid 满足条件, r = mid
else l = mid + 1; // mid 不满足条件, l = mid + 1
}
cout << l << '\n';
return 0;
}
输入格式
输入包含 行
第 行包 个整数 ，表示数组的长度和要分割的数量。
第 行包含 个整数，用空格分开，表示数组 。
输出格式
输出 个子数组各自和的最大值的最小值
5 2
7 2 5 10 8
18
5 2
1 2 3 4 5
9
3 3
1 4 4
4
提示
【样例解释 1】
- 一共有 种方法将 分割为 个子数组。
- 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
- 因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
请思考后再点击查看提示
- 答案满足单调性，考虑二分枚举答案
- 要求的是最小的答案，注意二分的边界情况