题意：
给你n m然后给你n个数。让你把这n个数分为m个部分，每个部分都是连续的。问所有部分中的最大值最小的值。
做法：
二分。一开始上届是n个数的和。代表只分一组。
下届是n个数中最大的数。代表分n组；
如果结果是mid=（上届+下届）/2;那么根据mid看看能分多少组。组数大于m,代表mid比实际值小。下届变成mid+1.否则，上届变成mid-1;
[html]
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int a[100100];
int n,m;
int sw（int mid）
{
int s,num,i;
s=0;
num=1;
for（i=0;i<n;i++）
{
if（s+a[i]<=mid）
{
s+=a[i];
}
else
{
s=a[i];
num++;
}
}
if（num>m）return 1;
else return 0;
}
int main（）
{
int l,r,i,mid;
cin》n》m;
r=0;
l=0;
for（i=0;i<n;i++）
{
scanf（"%d",&a[i]）；
r+=a[i];
if（a[i]>l）l=a[i];
}
mid=（l+r）/2;
while（l<r）
{
if（sw（mid））l=mid+1;
else r=mid-1;
mid=（l+r）/2;
}
cout《mid《endl;
return 0;
} |