资深光能
题目描述 Description
伐木工小光头今天在森林里砍树，获得了N段木材，已知这些木头很粗，而且头尾相连。现在有许多载木头用的卡车，卡车的车厢长度不同，宽度跟这些木头的粗细一样，且车厢长度越长使用费用越贵。现在他的老板想租M辆一样的卡车按木材的排列顺序来运这些木材，就问小光头要运完这些木头，花费最少的时候卡车长度是多少。聪明的你知道该怎么帮助小光头回答老板吗？
例如这堆木材长度为4 2 4 5 1，要分成3辆车运输。将其如下分配：[4 2][4 5][1]，第一辆车厢需要长度为6，第二辆车厢需要长度为9，第三辆车厢需要长度为1，需要卡车车厢长度最大值为9。将其如下分配：[4][2 4][5 1]，第一辆车厢需要长度为4，第二辆车厢需要长度为6，第三辆车厢需要长度为6，需要卡车车厢长度最大值为6。并且无论如何分配，需要卡车车厢长度最大值不会小于6。所以可以得到要将5段木材4 2 4 5 1要分成3辆车运输的话，卡车车厢长度6时最便宜。
输入描述 Input Description
第一行包含两个正整数N，M。
第二行包含N个空格隔开的非负整数Ai，含义如题目所述。
输出描述 Output Description
一个正整数，即每段和最大值最小为多少。
样例输入 Sample Input
5 3 4 2 4 5 1
样例输出 Sample Output
6
数据范围及提示 Data Size & Hint
对于20%的数据，有N≤10；
对于40%的数据，有N≤1000；
对于100%的数据，有N≤100000，M≤N，Ai 之和不超过10^9 。
跪求思路
中级光能
这一题目，是求解转判定。
我们定义一个put函数，检查长度为s时是否可以全部放入，
bool put(int s){
int cnt=1,p=0;
for(int i=1;i<=n;i++){
if(a[i]>s){
return 0;
}
else if(a[i]+p>s){
cnt++;
p=a[i];
}
else{
p+=a[i];
}
}
return cnt<=m;
}然后用二分（别跟我说二分你不会）在1到所有木材长度和（在输入时用sum累加得到）查找
int binsearch(int sum){
int l=1,r=sum;
while(l<r){
int mid=(l+r)/2;
if(put(mid))r=mid;
else l=mid+1;
}
return l;
}最后输出binsearch（sum）。
豆豆拿来！
资深光能
ding
中级天翼
二分，你还没学到吧。
下次刷题记得看数据范围
新手光能
@包
中级天翼
资深光能
顶
