题目地址：http://59.77.139.92/Problem.jsp?pid=2485
数列分段II
TimeLimit:1000MS MemoryLimit:128MB
64-bit integer IO format:%lld
Problem Description
对于给定的一个长度为N的正整数数列A[i]，现要将其分成M（M≤N）段，并要求每段连续，且每段和的最大值最小。
关于最大值最小：
例如一数列4 2 4 5 1要分成3段
将其如下分段：
[4 2][4 5][1]
第一段和为6，第2段和为9，第3段和为1，和最大值为9。
将其如下分段：
[4][2 4][5 1]
第一段和为4，第2段和为6，第3段和为6，和最大值为6。
并且无论如何分段，最大值不会小于6。
所以可以得到要将数列4 2 4 5 1要分成3段，每段和的最大值最小为6。
Input
输入的第1行包含两个正整数N，M，第2行包含N个空格隔开的非负整数A[i]，含义如题目所述。
(N≤100000，M≤N， A[i]之和不超过109。)
Output
输出仅包含一个正整数，即每段和最大值最小为多少。
SampleInput
5 3 4 2 4 5 1
SampleOutput
6
分析：由题 需要推出最小值可能在的范围。
然后将这个范围进行二分，看其中的值能不能实现。
对于每个值，我们需要推出实现当前的值最少需要的段数，
如果段数大于m则不成立。
代码如下：
#include <bits/stdc++.h> using namespace std; typedef long long ll; int c[100100]; int n,m; int check(int mid) { int sum=0; int num=1; for(int i=0;i<n;i++) { if(sum+c[i]<=mid)sum+=c[i]; else num++,sum=c[i]; } // cout<<"num"<<num<<endl; if(num>m)return 0; else return 1; } int main() { int l,r,mid,ans; while(cin>>n>>m) { l=0; r=0; for(int i=0;i<n;i++) cin>>c[i],l=max(c[i],l),r+=c[i]; while(l<r) { // cout<<"l="<<l<<endl; // cout<<"r="<<r<<endl; mid=(l+r)/2; if(check(mid))r=mid; else l=mid+1; } cout<<r<<endl; } return 0; }