P1182 数列分段 Section II

原题链接

作为二分答案的入门题非常合适。

很典型的二分答案。但是这题有一个坑点，left的值不能设为0这种确定的值，而是应该设为这个数组的最大值。

这道题警示了我二分答案的一个重要前提：确定合理的二分区间。

题解

首先，判断单调性，对于一个最大值mid，如果能够满足check（），那么mid+1，mid+2，也可以满足。

bool check(int mid){
    int cnt=1,sum_mid=1,sum=0;
    for (int i=1;i<=n;i++){
        if (sum+a[i]<=mid) sum+=a[i];
        else sum=a[i],sum_mid++;
    }
    return sum_mid<=m ? true :false;
}

接下来，确定二分区间，极端情况下，分段区间m=n的话最大值的最小值就是这个数组的最大元素。

但是这种情况下，如果mid取了0，check（）的返回值也是true（可以自己动手试一下）。

所以二分区间不能够草率的从0开始。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],m,n;
bool check(int mid){
    int cnt=1,sum_mid=1,sum=0;
    for (int i=1;i<=n;i++){
        if (sum+a[i]<=mid) sum+=a[i];
        else sum=a[i],sum_mid++;
    }
    return sum_mid<=m ? true :false;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int left=0,right=0;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        left=max(a[i],left);
        right+=a[i];
    }
    while (left+1<right){
        int mid=left+(right-left>>1);
        if (check(mid)) right=mid;
        else left=mid;
    }
    cout<<right;
    return 0;
}