poj Monthly Expense(最大值最小化)

Monthly Expense

题目链接：Click Here~

题目分析：

给出N个数，要求你合并连续的数，使其合并在满足不差过M个合并后的集合的时候，不超过M个集合的和的最大值最小。

思路分析:

1、二分集合的和的最小值。

2、C：判断是否满足集合不超过M个？

#include 
  
   
#include 
   
     #include 
    
      using namespace std; const int MAXN = 100000 + 10; const int INF = ~0U >> 2; int mony[MAXN]; int N,M; bool C(int m){ int j,cnt = 0; for(int i = 0;i < N;i = j){ if(mony[i] > m) return false; int sum = 0; j = i; while(j < N&&sum + mony[j] <= m){ sum += mony[j]; ++j; } cnt++; } return cnt <= M; } void solve(){ int lb = -1,ub = INF; while(ub - lb > 1){ int mid = (lb + ub) / 2; if(C(mid)) ub = mid; else lb = mid; } printf("%d\n",ub); } int main() { while(~scanf("%d%d",&N,&M)){ for(int i = 0;i < N;++i) scanf("%d",&mony[i]); solve(); } return 0; } 
    
   
  

??