Monthly Expense POJ - 3273

Monthly Expense POJ - 3273 题目地址

题意

Farmer john 知道接下来n天里每天花多少钱, 他想把接下来的n天划分m个fajomonths, 问怎样划分, 使的花费最大的哪一个fajomonths花费最小

分析

1 题目已经说了这么清楚, 肯定是二分搜索啦, 最小化最大值, 二分花费, 只不过本题需要注意的是r = 这n天里花费最大的那一天的花费

参考代码

(好吧,笨笨的我写了好长时间, wrong了好多次)

#include <iostream>
#include <cstdio>
#define fo0(i,n) for(int i = 0; i < n;+++i)
#define fo1(i,n) for(int i = 1; i <= n; ++i)
using namespace std;
const  int LEN = 100000+4;

int cost[LEN];
int N,M;
bool check(int mid)//判断函数
{
    long long week = 0;
    long long sum = 0;
    for(int i = 1;i <= N; ++i)
    {
        sum+=cost[i];
        if(sum>mid)
           {
               sum = cost[i];
               week++;
           }
       else if(sum == mid)
       {
           sum = 0;
           week++;
       }
        if(week>M)
         return false;
    }
    if(sum!=0)
        ++week;
    if(week<=M)
    return true;
    else
    return false;

}
int main()
{

    cin>>N>>M;
    int Max = 0;
    fo1(i,N)
   {
        scanf("%d",&cost[i]);
        if(cost[i]>Max)
            Max = cost[i];
   }
    int l = Max,r = 0x7fffffff;
   // cout<<r<<endl;
    int mid;
    int ans;
    while(r-l>1)//二分搜索
    {
        mid = l+(r-l)/2;
        if(check(mid))
         {
                ans = mid;
                r = mid-1;
         }
        else
            l = mid+1;
    }
    if(check(l))
       cout<<l<<endl;
    else if(check(r))
        cout<<r<<endl;
    else
        cout<<ans<<endl;
    return 0;
}