数列分段 Section II
链接：https://www.luogu.com.cn/problem/P1182
题目描述
对于给定的一个长度为 \(N\) 的正整数数列 \(A_{1\sim N}\)，现要将其分成 \(M\)（\(M\leq N\)）段，并要求每段连续，且每段和的最大值最小。
关于最大值最小：
例如一数列 \(4\ 2\ 4\ 5\ 1\) 要分成 \(3\) 段。
将其如下分段：
\[[4\ 2][4\ 5][1] \]第一段和为 \(6\)，第 \(2\) 段和为 \(9\)，第 \(3\) 段和为 \(1\)，和最大值为 \(9\)。
将其如下分段：
\[[4][2\ 4][5\ 1] \]第一段和为 \(4\)，第 \(2\) 段和为 \(6\)，第 \(3\) 段和为 \(6\)，和最大值为 \(6\)。
并且无论如何分段，最大值不会小于 \(6\)。
所以可以得到要将数列 \(4\ 2\ 4\ 5\ 1\) 要分成 \(3\) 段，每段和的最大值最小为 \(6\)。
输入格式
第 \(1\) 行包含两个正整数 \(N,M\)。
第 \(2\) 行包含 \(N\) 个空格隔开的非负整数 \(A_i\)，含义如题目所述。
输出格式
一个正整数，即每段和最大值最小为多少。
样例 #1
样例输入 #1
5 3
4 2 4 5 1
样例输出 #1
6
提示
对于 \(20\%\) 的数据，\(N\leq 10\)。
对于 \(40\%\) 的数据，\(N\leq 1000\)。
对于 \(100\%\) 的数据，\(1\leq N\leq 10^5\)，\(M\leq N\)，\(A_i < 10^8\)， 答案不超过 \(10^9\)。
解答
- 用二分答案的思想：这个其实我想到了，但是没法做，当时没思路
- 忽略了用段数来反映区间和
- 也就是当前最大值，判断最多构成多少段，如果当前段数比预期小，说明我们选的最大值太大了，如果段数过大，说明我们选的最大值过大了
- 注意左端点取值，从一个数的最大值开始，也就是将它划分为一段，不能从 0 开始，会被 hack
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N];
int n, m;
bool check(int x)
{
int cnt = 0;
LL sum = 0;
for (int i = 0; i < n; i++)
{
if (sum + a[i] <= x) sum += a[i];
else sum = a[i], cnt++;
}
// 注意这个判断
// 这里取小于，不可取等，因为段数等，可能还有更好的数，过小的，说明数过大
// 但是这里注意不用减减，因为二分只需保证一个加加或减减，否则用以 TLE
// 为啥不用考虑，因为下面 else 将这里也考虑了，
// 就算段数等，也让它加加，找到段数等最大的数，这里 r 不变就体现处作用了
if (cnt < m) return true;
else return false;
}
int main()
{
cin >> n >> m;
int l = 0, r = 1e9;
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
l = max(l, a[i]);
}
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l;
return 0;
}
说明BUG
input
5 4
1 2 3 4 5
output
5
- 上述是一个被 hack 的数据，也就是为啥不从 0 或 1 开始，左端点
- 当时想着虽然现在小，但是不会逐渐增加吗
- 实际有问题，增加也就是走了 else ，但是存在不走
- 也就是前面足够小，让段数减的慢，恰好让后面每个数都成为了单独的一段，而这单独的一段又比 mid 大
- 这就是问题所在了，会让输出比实际输出小