【POJ 3273】 Monthly Expense (二分)

一个农民有块地 他列了个计划表 每天要花多少钱管理 但他想用m个月来管理 就想把这个计划表切割成m个月来完毕 想知道每一个月最少花费多少 每一个月的花费是这个月的花费加和 必须按计划表的顺序来

全部天中花费中最大花费作为下界 全部花费加和作为上界 二分上下界间的花费可能 找出最少每月花费就可以

代码例如以下:

#include <iostream>

#include <cstdio>

using namespace std;

int ned[100000],n,m;

bool can(int x)//推断是否可行

{

    int i,sum = 0,cnt = 1;

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

    {

        sum += ned[i];

        if(sum > x)//加上这天后此划分超过x 割开

        {

            sum = ned[i];

            cnt++;

        }

    }

    if(cnt > m) return false;//划分块数>m 不可行

    return true;

}

int main()

{

    //freopen("in.in","r",stdin);

    int l,r,i,mid,ans;

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

    r = l = 0;

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

    {

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

        r += ned[i];

        l = max(l,ned[i]);

    }

    while(l <= r)

    {

        mid = (l+r)>>1;

        if(can(mid)) //可按mid划分的时候 此题数据真水 開始二分写挫了 还过了 3 2 4 4 4这组就能卡掉

        {

            ans = mid;

            r = mid-1;

        }

        else l = mid+1;

    }

    printf("%d\n",ans);

    return 0;

}