组长偏头痛
序号：#28难度：非常难时间限制：1000ms内存限制：10M
描述
临近年底，组长突然患上了偏头痛的毛病，因为他最近从产品经理那里收到了好多需求，需要按排组员尽快完成。 现在用一个数组来表示各个需求需要完成的时间，数组A包含n个元素，表示n个需求以及各个需求需要的时间。现在有个k个组员，因为需求有相关性，每个人只能完成连续一段编号的需求，比如A[1],A[2]由第一个人完成，但是不能A[1],A[3]由第一个人完成，求最少需要的时间完成所有需求。
举例：总共两位组员，三个需求，分别需要3,2,4个小时。第一位组员完成前两个需求，第二位组员完成第三个需求，需要5小时
输入
使用分号(;)分隔两组数据。 第一组为一个整数，表示组长手下一共有几位组员。 第二组为一个使用逗号(,)分隔的数组，表示每个需求消耗的工时。
输出
一个整数，表示完成所有需求所使用的最少时间。
输入样例
2;3,2,4
复制样例
输出样例
5
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int m;
int a[1005];
char buf[100005];
int f(int v)
{
if(v==0)return 1;
int res=0;
while(v>0)
{
res++;
v/=10;
}
return res;
}
bool read()
{
if(scanf("%s",buf)==1)
{
n=0;
int v;
char *p = strtok(buf,";");
sscanf(p,"%d",&v);
int len=f(v)+1;
m=v;
p=strtok(buf+len,",");
while(p)
{
sscanf(p,"%d",&v);
a[n++]=v;
p = strtok(NULL,",");
}
return true;
}
else return false;
}
bool ok(int mid)
{
int cnt=1;int now=0;
for(int i=0;i<n;i++)
{
if(a[i]+now<=mid)now+=a[i];
else {
if(a[i]<=mid)
{
cnt++;now=a[i];
}
else return false;
}
}
return cnt<=m;
}
int main()
{
// freopen("in.txt","r",stdin);
while(read())
{
int L=0;int R=0x3f3f3f3f;int mid;
while(R-L>1)
{
mid=(L+R)/2;
if(ok(mid))R=mid;
else L=mid;
}
int ans=R;
printf("%d
",ans);
}
return 0;
}