1 条题解

  • 0
    @ 2023-1-10 13:31:07
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    #include<queue>
    using namespace std;
    int n,m,x[100005],sum=0,max1=0;
    int judge(int sum1)//判断距离为d时能否放下c头牛
    {
        int num=1;
        int temp=0;
        for(int i=0;i<n;i++)
        {
            temp+=x[i];
            if(temp>sum1)
            {
                num++;
                temp=x[i];
            }
        }
        if(num>m)return 1;
        return 0;
    }
    int main()
    {
        cin>>n>>m;
        for(int i=0;i<n;i++)
        {
            cin>>x[i];
            sum+=x[i];
            if(x[i]>max1)max1=x[i];
        }
        int l=max1,r=sum;//r表示最大距离
        while(l<r)
        {
            int mid=(l+r)/2;//mid=l+r>>1;mid二分距离
            if(judge(mid))l=mid+1;//如果所求每段和>mid,增大试探
            else r=mid;//如果所求每段和<=mid,减小试探
        }
        cout<<r<<endl;
        return 0;
    }
    

    信息

    ID
    296
    时间
    1000ms
    内存
    512MiB
    难度
    10
    标签
    递交数
    2
    已通过
    1
    上传者