题目：http://poj.org/problem?id=3273
题意：把n个数分成m份，使每份的和尽量小，输出最大的那一个的和。
思路：二分枚举最大的和，时间复杂度为O(nlog(sum-max));
一道很好的题。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int maxn = +;
int a[maxn]; int main()
{
int n, m, i, Max, sum;
while(~scanf("%d%d", &n, &m))
{
Max = -;
sum = ;
for(i = ; i < n; i++)
{
scanf("%d", &a[i]);
sum += a[i];
if(Max < a[i])
Max = a[i];
}
int high = sum, low = Max, mid;
while(high>low)
{
mid = (high+low)/;
int cou = , w = ;
for(i = ; i < n; i++)
{
w += a[i];
if(w>mid)
{
cou++; //cou记录最大值为mid的情况下，可以分成几份
w = a[i];
}
}
if(cou>m)
low = mid+;
else
high = mid-;
}
printf("%d\n", high);
}
return ;
}
以后还是用这种形式的二分吧
while(left<right)
{
if()
left=mid+1;
else right=mid;
}
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int maxn = +;
int a[maxn]; int main()
{
int n, m, i, Max, sum;
while(~scanf("%d%d", &n, &m))
{
Max = -;
sum = ;
for(i = ; i < n; i++)
{
scanf("%d", &a[i]);
sum += a[i];
if(Max < a[i])
Max = a[i];
}
int high = sum, low = Max, mid;
while(high > low)
{
mid = (high+low)/;
int cou = , w = ;
for(i = ; i < n; i++)
{
w += a[i];
if(w>mid)
{
cou++;
w = a[i];
}
}
if(cou <= m)
high = mid;
else
low = mid+;
}
printf("%d\n", low);
}
return ;
}