POJ 3273 Monthly Expense(二分)
题意：给出农夫在n天中每天的花费，要求把这n天分作m组，每组的天数必然是连续的，要求分得各组的花费之和应该尽可能地小，最后输出各组花费之和中的最大值
分析：二分搜索的经典题目。。。
#include <cstdio>#include <iostream>#include <cstring>#define N 100050using namespace std ;int n , m ; //n 代表天数，m代表要分成的区间数int money[N] ;boolDivide ( int const m_max ){ int sum ; sum = 0 ; int group ; group = 1 ; //注意这个初始化 for ( int i = 1 ; i <= n ; i ++ ) { int temp ; temp = sum + money[i] ; if ( temp <= m_max ) //注意这个判断 { sum += money[i] ; } else { sum = money[i] ; group ++ ; } } return group > m ? true : false ;//注意，当前分组大于实际分组则表示m_max 值小了,grou == m 的情况应返回false 题意:minimize the expenses of the fajomonth}voidModify_Low_High ( int & low , int & high ){ for ( int i = 1 ; i <= n ; i ++ ) { high += money[i] ; if ( low < money[i] ) { low = money[i] ; } } return ;}voidSolve ( ){ int low , high ; //定义二分搜索的上下限 low = high = 0 ; Modify_Low_High ( low , high ) ; int mid ; while ( low <= high ) //二分搜索 { mid = ( low + high ) / 2 ; bool flag ; flag = Divide ( mid ) ; if ( flag ) //当前mid 作为highest spending 小了 { low = mid + 1 ; } else { high = mid - 1 ; } } printf ("%d\n" , mid ) ; return ;}intmain ( ){ while ( EOF != scanf ("%d%d" , & n , & m ) ) { for ( int i = 1 ; i <= n ; i ++ ) { scanf ("%d" , & money[i] ) ; } Solve ( ) ; } return 0 ;}