【题目描述】

农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来N(1 ≤N≤ 100,000) 天里每天需要的开销。

约翰打算为连续的M(1 ≤M≤N) 个财政周期创建预算案，他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天，每天被恰好包含在一个fajo月里。

约翰的目标是合理安排每个fajo月包含的天数，使得开销最多的fajo月的开销尽可能少。

【输入描述】

第一行包含两个整数N,M，用单个空格隔开。

接下来N行，每行包含一个1到10000之间的整数，按顺序给出接下来N天里每天的开销。

【输出描述】

一个整数，即最大月度开销的最小值。

【样例输入】

7 5  100  400  300  100  500  101  400

【样例输出】

500

【题目分析】

• 题目描述的过于复杂，实际上就是二分，N是天数，M是要分成的财政周期。

• 区别：月度开销的值应该在 每天开销最大值 和 每天开销的总和 之间，通过二分法不断逼近。judge函数判断按照mid开销所分的周期，如果周期大于给定周期M，则可以增加开销，反之，减小开销。

【参考代码】

#include<iostream>  #include<cstdio>  #include<cstdlib>  #include<cstring>  #include<cmath>  #include<algorithm>  #include<string>  #define INF 999999999  #define N 1000001  #define MOD 1000000007  #define E 1e-3  using namespace std;  int n,m,a[N];  int judge(int x)  {      int money=0,month=0,d,i;      for(i=1;i<=n;i++)      {          money+=a[i];          if(money>=x)          {              month++;              if(a[i]<x)                  money=a[i];              else                  return 1;          }      }      return month>=m;  }  int main()  {      int left,right,mid;      int tot=0;      cin>>n>>m;      for(int i=1;i<=n;i++)      {          cin>>a[i];          tot+=a[i];      }      left=1;      right=tot;      while(left+1<right)      {          mid=(left+right)/2;          if(judge(mid))              left=mid;          else              right=mid;      }      if(judge(left))          cout<<left<<endl;      else          cout<<right<<endl;      return 0;  }

(adsbygoogle = window.adsbygoogle || []).push({});