题目链接

思路如下

题意：这一题让我们在一个 n 个数的序列，分成连续的的 m个子串(一个数也可是一个子串)，是在所有子串中和最大的子串的和最小.

思路：我们可以用二分法来一个一个枚举答案，二分的上限为：序列中 n 个数之后。下限为：数列中最大的数，通过枚举一个数，看这个数是不是答案，我们可以考虑：在这个枚举的数字的基础上能不能把 m子串分割出来，能分割出来来我们调整答案的下限，分割不出来调整答案的上限；

题解如下

#include<iostream>

#include<algorithm>

using namespace std;

const int Len  = 1e5 + 5;

int ar[Len];

int m,n;

bool group(int mid)

{

    int sum = 0;

    int cnt = 1;

    for(int i = 0; i < m; i ++)

    {

        if(sum + ar[i] <= mid)

        {

            sum += ar[i];

        }

        else

        {

            sum = ar[i];

            cnt ++;

        }

    }

    if(cnt > n)

        return true;

    else

        return false;

}

void Binary_search(int l,int r)

{

    int mid;

    while(l <= r)

    {

        mid = (l + r) / 2;

        if(group(mid))

        {

            l = mid + 1;

        }

        else

        {

            r = mid - 1;

        }

    }

    printf("%d",mid);

}

int main()

{

    //freopen("A.txt","r",stdin);

    scanf("%d %d",&m,&n);

    int sum = 0;

    int mx = -1;

    for(int i = 0; i < m; i ++)

    {

        scanf("%d",&ar[i]);

        sum += ar[i];

        mx = max(mx , ar[i]);

    }

    Binary_search(mx,sum);

    return 0;

}

巴特西

POJ 3273Monthly Expense（二分答案）

题目链接

思路如下

题解如下

最新文章

热门文章