POJ 3723 Monthly Expense 二分

本文主要是介绍POJ 3723 Monthly Expense 二分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给你n个值，要求将其划分成m部分（顺序不能打乱），如何划分使得最大部分的值最小。

题解：二分，对于每一个中间值，检测一次。

#include<cstdio>
int N, M;
int spend[200000];
bool check ( int num )
{
int i, sum, cnt = 0;
for ( i = 0; i < N; )
{
sum = 0; cnt++;
while ( i < N && sum + spend[i] <= num )
sum += spend[i++];
if ( sum == 0 || cnt > M ) return false;
}
return true;
}
int bfind ( int left, int right )
{
while ( left + 1 < right ) //防止出现left=mid的死循环
{
int mid = (left+right)/2;
if ( check(mid) ) right = mid; //始终保持一边是合法的
else left = mid + 1;
}
//因为left<=right，所以如果left是合法的那么它比right更优
if ( check(left) ) return left; 
else return right;
}
int main()
{
scanf("%d%d",&N,&M);
int sum = 0, ret;
for ( int i = 0; i < N; i++ )
{
scanf("%d",&spend[i]);
sum += spend[i];
}
ret = bfind ( sum / N, sum );
printf("%d\n",ret);
return 0;
}

 

这篇关于POJ 3723 Monthly Expense 二分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---