1436：数列分段II

逃离我推掉我的手 2021-12-17 01:09 206阅读 0赞

### 1436：数列分段II ###

![1606003-20190608110126242-506621117.png][]

![1606003-20190608110158243-422112442.png][]

**题解**

二分答案

我们最终答案的取值区间是\[  max(a\[i\])  ,   ∑a\[i\]  \]

设定 l=max(a\[i\]) , r=∑a\[i\]  , mid不断二分

mid表示每段和的最大值，也就是每段和都不超过mid

放到check函数里，计算一下在mid为最大值的情况下可以分成多少段

如果段数 cnt > m ，说明这个mid小了，它还可以再大一点

如果段数 cnt <= m , 说明这个mid大了，那么它就要小一点了，由于此时cnt可能等于m,这个mid为候选答案，记录下来（如果他是真正答案，最后输出的就是他，否则他会被更新为一个更小的）

**代码**

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    #include<string>
    #include<queue>
    #include<functional>
    
    using namespace std;
    
    int n,m,ans,l=0,r=0;
    int a[100001];
    int sum[100001]; 
    
    int check(int x)
    {
        int cnt=1,now=0;
        for(int i=1;i<=n;i++)
        {
            if(now+a[i]<=x) now+=a[i];
            else
            {
                cnt++;
                now=a[i];
            }
        }
        return cnt<=m;
    }
    
    int main()
    {
         scanf("%d%d",&n,&m);
         for(int i=1;i<=n;i++)
         {
             scanf("%d",&a[i]);
             l=max(l,a[i]);
             r+=a[i];
         }
         
         while(l<=r)
         {
             int mid=(r+l)/2;
             if(check(mid)) 
             {
                 ans=mid;
                 r=mid-1;
            }
            else l=mid+1;
         }
           
        printf("%d",ans);
        
    }

转载于:https://www.cnblogs.com/xiaoyezi-wink/p/10990232.html

[1606003-20190608110126242-506621117.png]: /images/20211214/0ef04710ca2643c78bcdb4539ad08228.png
[1606003-20190608110158243-422112442.png]: /images/20211214/40a0a4da4b8b4d4b968f1d6600225804.png