poj 3273 Monthly Expense

点击打开链接poj 3273

思路：二分

分析：
1 题目给定n天的消费金额，已经要分成的m部分。现在问我们在所有可分的情况下，最大一部分的和的最小值。
2 如果m =1 ，那么最大的一部分就是sum；如果m = n，那么最大的一部分就是n个数的人最大值max；根据1=<m<=n可以知道这个ans肯定是在[max,sum]之间，那么我们就可以利用二分的思想，去二分这个ans，然后找到最小的并且满足条件的；
3 由于题目明确指出每一部分的天数是连续的，那么我们在判断是否满足的时候就只要枚举一些即可。
4 注意一下二分的上下界，二分的上下界是有严格要求的。

代码：

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

#define MAXN 100010

int n , m , sum , Min;
int money[MAXN];

void solve(){
   int left , right , mid;

   left = Min , right = sum;
   while(left < right){
      mid = left+(right-left)/2;/*这里为了不溢出采用这个方法*/
      
      int tmpSum = 0;
      int count = 1;/*至少有一个组*/
      for(int i = 0 ; i < n ; i++){
         tmpSum += money[i];
         if(tmpSum > mid){
           tmpSum = money[i];
           count++;
         }
      }

      if(count <= m)/*如果分的组刚好小于等于m说明mid值大了*/
        right = mid;
      else
        left = mid+1;
   }
   printf("%d\n" , left);
}

int main(){
   while(scanf("%d%d" , &n , &m) != EOF){
       Min = 0 , sum = 0;
       for(int i = 0 ; i < n ; i++){
          scanf("%d" , &money[i]);
          sum += money[i];
          Min = max(Min , money[i]);
       }
       solve();
   }
   return 0;
}