1.4.4 数列分段（题解:二分）

我们同样以一个题目继续讲解二分的应用。

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 <cstdio>
     
    
   

    

     

    
    

     

      #include <algorithm>
     
    
   

    

     

    
    

     

      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<n; 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<n; 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