【二分】数列分段 Section II

$Link$

$luogu$ $P1182$

$Description$

对于给定的一个长度为N的正整数数列$A-i$，现要将其分成$M(M\le N)$段，并要求每段连续，且每段和的最大值最小。

关于最大值最小：

例如一数列$42451$要分成$3$段

将其如下分段：

$[4$ $2][4$ $5][1]$

第一段和为$6$，第$2$段和为$9$，第$3$段和为$1$，和最大值为$9$。

将其如下分段：

$[4][2$ $4][5$ $1]$

第一段和为$4$，第$2$段和为$6$，第$3$段和为$6$，和最大值为$6$。

并且无论如何分段，最大值不会小于$6$。

所以可以得到要将数列$42451$要分成$3$段，每段和的最大值最小为$6$。

$Input$

第1行包含两个正整数$N，M$。

第2行包含$N$个空格隔开的非负整数$A_i$ ，含义如题目所述。

$Output$

一个正整数，即每段和最大值最小为多少。

$Sample$ $Input$

5 3 4 2 4 5 1

$Sample$ $Output$

6

$Hint$

对于$20$的数据，有$N\le 10$；

对于$40$的数据，有$N\le 1000$；

对于$100$的数据，有$N\le 100000,M\le N,A_i之和不超过10^9$

$Train$ $of$ $Thought$

这题我用二分来做 因为要涉及到区间和，所以，前缀和优化，然后二分答案 具体看代码

$Code$

#include<iostream> #include<cstdio> int n, m, sum[100005]; using namespace std; bool check(int mid) { int end = 1, start = 0, cnt = m; while (cnt--) { while (sum[end] - sum[start] <= mid && end <= n) end++;//枚举当前分段的右端点 start = end - 1;//记录下一段的左端点 if (start == n) return 1; } } int main() { int ans = 0; scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) { int x; scanf("%d", &x); sum[i] = x + sum[i - 1];//前缀和 } int left = sum[1], right = sum[n]; while (left <= right) { int mid = (left + right) >> 1; if (check(mid)) ans = mid, right = mid - 1;//二分的答案其实就是题目的答案 else left = mid + 1; } printf("%d", ans); return 0; }