POJ 3273 Monthly Expense 二分

题目链接:http://poj.org/problem?id=3273

题意

给出包含n个元素的数组,将这n个元素分成最多m段,问各种分法中每段和的最大值得最小值是多少

题解

最小化最大值问题,使用二分进行求解,需要注意的是,在不断二分的时候边界更新的时候,当中间值不满足条件的时候,新的区间应该是[mid+1,r],满足条件的时候新的区间应该是[l,mic].即要排除掉不满足条件的数

代码 ing namespace std;

#define INF 0x3f3f3f3f
typedef long long ll;
const int maxn=100010;
int n,m;
int d[maxn];

bool judge(int s)
{
int num=0,tmp=0;
for(int i=0;i<n;i++)
{
if(tmp+d[i]<=s) tmp+=d[i];
else
{
//cout<<tmp<<” “;
tmp=d[i];
num++;
}
}
if(tmp) num++;
//cout<<num<<endl;
return num<=m;
}

int fun(int maxv,int sum)
{
int l=maxv,r=sum,mid;
while(l>1);
mid=(l+r)/2;
//cout<<l<<” “<<r<<” “<<mid<<endl;
if(judge(mid)) r=mid;
else l=mid+1;
}
return l;
}

void solve()
{
while(scanf(“%d %d”,&n,&m)!=EOF)
{
int sum=0,maxv=0;
for(int i=0;i<n;i++)
{
scanf(“%d”,&d[i]);
sum+=d[i];
maxv=max(maxv,d[i]);
}
printf(“%d\n”,fun(maxv,sum));
}
}