数列分段`Section II`（二分

https://www.luogu.org/problemnew/show/P1182

洛谷上的题目。

以后如果遇到1e5什么的用二分试试！

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<string>
 7 #include<cmath>
 8 #include<set>
 9 #include<vector>
10 #include<stack>
11 #include<queue>
12 #include<map>
13 using namespace std;
14 #define ll long long
15 #define se second
16 #define fi first
17 const int INF= 0x3f3f3f3f;
18 const int N=1e5+5;
19 
20 int n,m;
21 int a[N];
22 
23 bool check(int x)
24 {
25     int s=0,cnt=1;
26     for(int i=1;i<=n;i++)
27     {
28         if(s+a[i]<=x){
29             s+=a[i];
30         }
31         else{
32             s=a[i];
33             cnt++;
34         }
35     }
36     return cnt<=m;// 如果区间数比要求的多，就返回0
37 }
38 
39 int main()
40 {
41     cin>>n>>m;
42     int l=0,r=0,mid,ans=0;
43     for(int i=1;i<=n;i++) scanf("%d",&a[i]),r+=a[i],l=max(l,a[i]);
44     
45     //必须 l>=a[i]; 这是一个WA点
46     while(l<=r)
47     {
48         mid=(l+r)>>1;
49         if( check(mid) ){
50             r=mid-1;
51             ans=mid;
52         }
53         else l=mid+1;
54     }
55     cout<<ans;
56 }