codevs 3278 最小m 段和问题

时间限制: 1 s

空间限制: 256000 KB

题目等级 : 黄金 Gold

题目描述 Description

给定 n 个整数(不一定是正整数)组成的序列，现在要求将序列分割为 m 段，每段子序列中的数在原序列中连续排列。如何分割才能使这 m 段子序列的和的最大值达到最小？

输入描述 Input Description

文件的第 1 行中有 2 个正整数 n 和 m。正整数 n 是序列的长度；正整数 m 是分割的断数。接下来的一行中有 n 个整数。

输出描述 Output Description

文件的第 1 行中的数是计算出的 m 段子序列的和的最大值的最小值。

样例输入 Sample Input

1 1

样例输出 Sample Output

数据范围及提示 Data Size & Hint

N<=1000,M<=N

二分做法点击传送

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int ans,l,r,n,m,i,a[+];

int judge(int now)

{

    int tot=,x=;

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

    {

        if(a[i]>now) return ;

        if(a[i]+x<=now)

        x+=a[i];

        else

        {

            x=a[i];

            tot++;

            if(tot>=m) return ;

        }

    }

    return ;

}

int main()

{

    cin>>n>>m;

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

    {

        cin>>a[i];

        r+=a[i];

    }

    while(l<=r)

    {

        int mid=(l+r)>>;

        if(judge(mid))

        {

            ans=mid;

            r=mid-;

        }

        else l=mid+;

    }

    cout<<ans;

}

巴特西

codevs 3278 最小m 段和问题

最新文章

热门文章