LiberOJ 10014 数列分段 II 二分

题意

给定长度为 \(N\) 的序列 \(A\)，要将其划分为连续的 \(M\) 段，并最小化每一段总和的最大值。

输入格式

第1行包含两个正整数 \(N,M\)

第2行包含 \(N\) 个空格隔开的非负整数 \(A_i\)，含义如题目所述。

输出格式

仅包含一个正整数，即每段和最大值最小为多少。

Input

5 3
4 2 4 5 1

Output

6

\(Note:\) 划分方式可以为：\([4,2][4][5,1]\)

Solution

我们二分答案，答案的左端点 \(l = \max_i(A_i)\)，右端点 \(r = \sum_i A_i\)
我们每次 \(check\) 答案的时候，统计段落数 \(cnt\).

如果 \(cnt\geq M\)，说明我们此时需要增大左端点（因为上限偏小，这样才会使得段落数变多）

\(Code:\)

点击查看代码

int n,m; const int N = 1e5+5; int a[N]; int sum[N];  bool check(int x){     int cnt=0;     int cur = 0;     for(int i=2;i<=n;i++){         if(sum[i]-sum[cur]>x){             cur = i-1;             cnt+=1;         }     }     if(cnt>=m) return true;     return false; }  int main(){     //ios::sync_with_stdio(false);     n = read();m = read();     int l=0,r;     for(int i=1;i<=n;i++)a[i] = read(),sum[i] = sum[i-1]+a[i],l = max(l,a[i]);     r = sum[n];     int ans = sum[n];     while(l<r){         int mid = (l+r)>>1;         if(check(mid)){             l=mid+1;         }         else{r=mid;}     }     cout<<r<<endl;  }

\(\\\)
这里的二分模板为：

点击查看代码

int bsearch_1(int l, int r) {     while (l < r)     {         int mid = l + r >> 1;         if (check(mid)) r = mid;         else l = mid + 1;     }     return l; }