P1182 数列分段`Section II` 二分

https://www.luogu.org/problemnew/show/P1182

做了这个题才知道二分的强大

这个题可以假设我们有n个果子 m个容器要能把果子全装进去那么容器最小可以是多小

很显然如果我们的容器每一个都能把全部的果子装进去那么一定是一种可行的解但不是最优的

容器最小是多小呢？至少要能装得下最大的果子

所以答案就在 maxAi 和 sumAi 之间进行二分查找即可

如果当前的mid是容器的容量，求出来需要多少容器如果比 m 多那么说明 mid 太小了如果小于等于 m 那么就看看还有没有可以更小一点的容量

#include<bits/stdc++.h>

using namespace std;

int n,m,a[];

void erfen(int l,int r)

{

    int i;

    if(l>=r)

    {

        cout<<l<<endl;

        exit();

    }

    int mid=(r+l)/;

    int sumn=;

    int k=;

    for(i=;i<n;i++)

    {

        sumn+=a[i];

        if(sumn>mid)

        {

            sumn=a[i];

            k++;

            if(k>m)

            break;

        }

    }

    if(k>m)

    {

        erfen(mid+,r);

    }

    else

    {

        erfen(l,mid);

    }

}

int main()

{

    int i,maxn=,sumn=;

    cin>>n>>m;

    for(i=;i<n;i++)

    {

        cin>>a[i];

        maxn=max(a[i],maxn);

        sumn+=a[i];

    }

    erfen(maxn,sumn);

}

巴特西

P1182 数列分段`Section II` 二分

最新文章

热门文章