//众神云集、群魔乱舞、以一抵百、砥砺前行//P1182 数列分段 Section II

忘是亡心i 2023-02-14 06:47 51阅读 0赞

## 题目描述 ##

[题目链接][Link 1]

## 题解 ##

使用二分答案。二分的对象是数段的和，二分的范围是1-1e10。

代码如下：

#include<algorithm>
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<string>
    #include<cstring>
    using namespace std;
    #define ll long long
    #define maxn 10000000000
    ll read()
    {
        
        ll ans=0,sign=1;
        char ch;
        ch=getchar();
        while(ch<'0'||ch>'9')
        {
        
            if(ch=='-')
                sign=-1;
            ch=getchar();
        }
        while(ch>='0'&&ch<='9')
        {
        
            ans=(ans<<1)+(ans<<3)+(ch^48);
            ch=getchar();
        }
        return ans;
    }
    int n,m;
    ll a[100005];
    bool cheak(ll tag)
    {
        
        ll temp=0;
        ll sum=0;
    for(int i=1;i<=n;i++)
    {
        
        if(temp+a[i]<=tag)
            temp+=a[i];
        else
        {
        
            if(a[i]>tag)
                return 0;
            temp=a[i];
            sum++;
        }
    }
    return (sum+1)<=m;
    }
    int main()
    {
        
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            a[i]=read();
        ll x=1,y=maxn,ans;
        while(x<=y)
        {
        
            ll mid=x+(y-x)/2;
            if(cheak(mid))
            {
        
                y=mid-1;
                ans=mid;
            }
            else
                x=mid+1;
        }
        cout<<ans<<'\n';
        return 0;
    }

[Link 1]: https://www.luogu.com.cn/problem/P1182