数列分段
对于给定的一个长度为N的正整数数列A[i]，现要将其分成M（M≤N）段，并要求每段连续，且每段和的最大值最小。
举例将4,2,4,5,1分成3段，有[4,2][4,5][1]、[4][2,4][5,1]两种分法，第一段每段和最大值为9，第二段每段最大值为6，输出6
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 100005 4 inline int read(){ 5 int s=0,w=1; 6 char ch=getchar(); 7 while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} 8 while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();} 9 return s*w; 10 } 11 int qy[N],l,r,n,m; 12 bool check(int x) 13 { 14 int sum=0,cnt=1; 15 for(int i=0;i<n;i++) 16 { 17 sum+=qy[i]; 18 if(sum>x) cnt++,sum=qy[i]; 19 } 20 if(cnt>m) return 1; 21 return 0; 22 } 23 int main() 24 { 25 n=read(),m=read(); 26 for(int i=0;i<n;i++) 27 { 28 qy[i]=read(); 29 r+=qy[i]; 30 l=max(l,qy[i]); 31 } 32 while(l<r) 33 { 34 int mid=(l+r)/2; 35 if(check(mid)) l=mid+1; 36 else r=mid; 37 } 38 cout<<r<<endl; 39 }