题目描述

对于给定的一个长度为N的正整数数列A[i]，现要将其分成M（M≤N）段，并要求每段连续，且每段和的最大值最小。

输入格式

输入文件divide_b.in的第1行包含两个正整数N，M，第2行包含N个空格隔开的非负整数A[i]，含义如题目所述。

输出格式

输出文件divide_b.out仅包含一个正整数，即每段和最大值最小为多少。

样例输入

5 3

4 2 4 5 1

样例输出

6

【题目 https://www.luogu.org/problemnew/show/1182】（蒟蒻不会弄链接，望大佬指点orz）

题解

“最大值最小”，二分的标志

二分最大值mid，检查时枚举每个数要放入已有的段还是另起一段，如果一个数放入已有段后，该段和不超过mid，那么放进去，否则另起一段，同时计数器加1.

最后把计数器和M比较，如果不比M大，说明当前mid值足够大，可以小一点，于是r=mid-1；否则说明当前mid值偏小，要大一点，于是l=mid+1。

计数器初始值为1，因为数列至少会被分成一段，（我第一次把计数器初始为0，样例过了，交上去居然全WA了(ㄒ _ ㄒ)）

 

#include 
     
      int n,m,a[100005],l,r,mid,ans;bool check(){    int s=1,sum=0;    for (int i=1;i<=n;i++)      if (sum+a[i]<=mid) sum+=a[i];      else s++,sum=a[i];      return (s<=m);  }int main(){    int i;    scanf("%d%d",&n,&m);    for (i=1;i<=n;i++)    {        scanf("%d",&a[i]);        r+=a[i];        if (a[i]>l) l=a[i];    }          while (l<=r)    {        mid=(l+r)>>1;        if (check()) r=mid-1,ans=mid;        else l=mid+1;    }      printf("%d",ans);    return 0;}