100
#LS1074. 【入门】分割数组的最小值-
ID: 104
传统题
100ms
64MiB
尝试: 51
已通过: 26
难度: 4
上传者:
【入门】分割数组的最小值
题目描述
给定一个非负整数数组 和一个整数 ，你需要将这个数组分成 个非空的连续子数组。
设计一个算法使得这 个子数组各自和的 最小值最大 。
- 提示：这是第 2 类二分问题的模板，不熟悉的同学可以参考：
老师的模板
#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 mid) { }
auto ok = [&](int mid) {
int d = 0;
for (int i = 0; i < n; i++) {
int sum = a[i];
// 在和小于过 mid 的前提下，每个子段尽可能选少的数
while (sum < mid && i + 1 < n) sum += a[++i];
if (sum < mid) return false; // 如果 sum < mid
if (++d >= k) return true; // 如果已经分成了 k 组
}
return d >= k; // 分的段数要 >= 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 + 1) / 2; // 注意：第 1 类二分, 这里需要 + 1
if (ok(mid)) l = mid; // mid 满足条件
else r = mid - 1; // mid 不满足条件
}
cout << l << '\n';
return 0;
}
输入格式
输入包含 行
第 行包 个整数 ，表示数组的长度和要分割的数量。
第 行包含 个整数，用空格分开，表示数组 。
输出格式
输出 个子数组各自和的最小值的最大值
5 2
7 2 5 10 8
14
5 2
1 2 3 4 5
6
3 3
1 4 4
1
提示
【样例解释 1】
- 一共有 种方法将 分割为 个子数组。
- 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
- 因为此时这两个子数组各自的和的最小值为14，在所有情况中最大。
请思考后再点击查看提示
- 答案满足单调性，考虑二分枚举答案
- 要求的是最小的答案，注意二分的边界情况
数据规模与限制
相关
在以下作业中: