我们同样以一个题目继续讲解二分的应用。
1.4.4 数列分段
Description
对于给定的一个长度为N的正整数数列A[1..N]A[1..N]A[1..N]，现要将其分成MMM（M≤NM≤NM≤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。
Input
第 1 行包含两个正整数 N,MN,MN,M。
第 2 行包含 NNN 个空格隔开的非负整数 AiA_iAi，含义如题目所述。
Output
一个正整数，即每段和最大值最小为多少。
Sample Input 1
5 3
4 2 4 5 1
Sample Output 1
6
Hint
对于 100% 的数据，1≤ N≤ 100,000，M≤N，A[i]≤ 1081 \le N \le 100,000， M≤N，A[i] \le 10^8 1≤ N≤ 100,000，M≤N，A[i]≤ 108
答案不超过10910^9109
#include
#include
int n, m;
int l, r, mid, ans;
int a[100010];
//二分答案，枚举出一个最大值，根据分组情况调整最大值，求出最优最大值。
/*
* check 函数
* 作用:
* 根据枚举出的最大值，来分组，根据分出的组数来调整最大值
* 变量:
* x : 枚举出的最大值
* sum : 分组时每组的和
* count : 分出的组数
*/
bool check(int x)
{
int sum=0, count=0;//t2: 组数 t1: 每组的和
for(int i=0; i if(sum+a[i]<=x)sum+=a[i]; //如果还是小于mid，就继续加上去 else //objective 1如果当前sum已经达到当前最大值应该怎么处理？ { sum=a[i]; //设置sum为当前数字,相当于换入下一组 count++; } } if(count>=m)return true;//objective 2 return false; } int main() { scanf("%d %d", &n, &m); for(int i=0; i scanf("%d", &a[i]); r += a[i]; l = std::max(l, a[i]); } while( l<=r ){ mid=(l+r)/2; if( check(mid) )l=mid+1;//如果最后的count是大于m的话，说明mid太小了，需要l往右移 else {//否则就是mid太大了 r=mid-1; } } printf("%d",l); return 0; } 显而易见，二分法给这种看似难以解决的最大最小问题提供了方法，利用二分枚举，降低了思维难度。 文章来源: blog.csdn.net，作者：irrationality，版权归原作者所有，如需转载，请联系作者。 原文链接：blog.csdn.net/weixin_54227557/article/details/120581055