题解：CF2028C Alice's Adventures in Cutting Cake

题目传送门

题目大意

你需要把有 n 个数的序列分为 m 或者 m+1 个连续的子序列。要求：每一个子序列中的数字之和需要大于等于 v。

如果能这样分配序列，并且有 m+1 的一个子序列，输出这些子序列的和中最大是多少（当只有 m 个子序列时，输出 0）。

否则，输出 -1。

思路

这道题显然是二分答案。

二分答案，之所以有答案两个字，就是因为其一般枚举所求问题的结果。

但是我们发现，我们只二分最大值的话，不确定他是哪一个区间，也就是不知道区间的左端点和右端点，比如 2 ~1~1~1~3。

对于这个序列，如果二分的值为 2（先不考虑正确性），那区间的左端点和右端点有两种情况。

显然，这对答案是有影响的。

所以，我们必须枚举其中一个端点，这里枚举 l。

直接展示代码，所有要注意的细节以及问题都体现在注释中。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int T; 
int n,m,v,a[200005],s[200005];
bool check(int L,int R){//判断其余数字能否组成 m 个以上区间 
    int g=0,l=1;
    for(int i=1;i<L;i++){
        if(s[i]-s[l-1]>=v) g++,l=i+1;
    }
    l=R+1; 
    for(int i=R+1;i<=n;i++){
        if(s[i]-s[l-1]>=v) g++,l=i+1;
    } 
    return g>=m;
}
void Main(){
    cin>>n>>m>>v;
    for(int i=1;i<=n;i++) cin>>a[i];
    //读入 
    int g=0,sum=0;
    for(int i=1;i<=n;i++){
        sum+=a[i];
        if(sum>=v) sum=0,g++;//能变成一个区间。 
    }
    if(g<m){
        cout<<"-1\n";
        return ;
    }
    int ans=0;
    //只有当整个序列不能分成 m 个和大于等于 v 的子序列时输出 -1。 
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
    //这里用前缀和优化求区间和 
    for(int l=1;l<=n;l++){
        int r=n;
        while(l<=r){
            if(check(l,r)){
                ans=max(s[r]-s[l-1],ans);
                break;
            }
            else r=l+(r-l)/2-1;
        }
    }
    //二分 
    cout<<ans<<"\n"; 
    return ;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>T;
    while(T--) Main();
    return 0;
}