题解：[ABC370F] Cake Division

· · 题解

提供一种 O(n\log n) 的已通过的算法，欢迎 Hack。

一、题意

给出一个长为 N 的环，要求分成 K 段，设第 i 段的总和为 S_i，求出 \min \limits_{i=1}^{K} \{ S_i \} 的最大值。

二、分析与做法

心路历程：开始和其他题解想的一样，先倍长破环为链，再考虑跳等等，但是没有想到倍增。同时鉴于我定义的状态，我只好不再破环为链，但歪打正着地想到了如下做法。

题目要求最大的最小值，我比较自然地想到二分答案。check 时需要一点贪心：如果我们定下一段的终点，我们希望前面划分的段数尽量多，同时最开始可能会剩下一段无法单独成段的边角料，我们则希望它尽可能大，以便后期我们把后面的边角料跟它配起来能尽量再成为一段。

因此，我们定义：在已知每段的和最小为 mid 的前提下，f_i 为以 i 号分割线为一段的终点线，前部所能划分的最多段数，g_i 为达到 f_i 时第一段可能的最右侧的起点线；f_i'，g_i' 为后部的定义类似的两个量。如果我们最后求完所有的以上四个量，那么存在一种方案划分了 i 号分割线当且仅当 f_i+f_i'+[\sum \limits_{j=1}^{g_i} A_j+\sum \limits_{j=g_i'+1}^{N} A_j \geq mid] \geq K，mid 合法当且仅当存在一个分割线可能被划分。

下面考虑如何求得以上四个量，以前两个为例。我们可以用双指针维护最后一个 l 满足 l 和 i 两个分割线间可以成为合法的一段。考虑到 l 变大，要么 f_l 变大，要么 g_l 不降，所以是不劣的。所以如果 \sum \limits_{j=l+1}^{i} A_i \geq mid，则 f_i=f_l+1,g_i=g_l；否则（此时一定有 l=0）f_i=0,g_i=i。

于是我们可以二分 mid，时间复杂度 O(n\log n)。

三、代码

如下，一些细节记在注释里了。

#include<iostream>
using namespace std;
const int N=2e5+10;
int n,k,a[N],vis[N],ans;
long long qzh[N],f[N],g[N],f2[N],g2[N];//以切割线为准 
int check(long long x){
    int l=0,flag=0;
    for(int i=1;i<=n;i++){
        while(qzh[i]-qzh[l+1]>=x) l++;
        if(qzh[i]<x) f[i]=0,g[i]=i;
        else f[i]=f[l]+1,g[i]=g[l];
    }l=n;
    for(int i=n;i;i--){
        while(qzh[l-1]-qzh[i]>=x) l--;
        if(qzh[n]-qzh[i]<x) f2[i]=0,g2[i]=i;
        else f2[i]=f2[l]+1,g2[i]=g2[l];
    }
    for(int i=1;i<=n;i++){
        if(f[i]+f2[i]>=k) vis[i]=1,flag=1;
        else if(f[i]+f2[i]==k-1){
            if(qzh[g[i]]+qzh[n]-qzh[g2[i]]>=x) vis[i]=1,flag=1;
            else vis[i]=0;
        }
        else vis[i]=0;
    }return flag;
}
int main(){
    cin>>n>>k;ans=n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),qzh[i]=qzh[i-1]+a[i];
    long long l=1,r=2e9+10,mid;
    while(l<r){
        mid=(l+r+1)/2;
        if(check(mid)) l=mid;
        else r=mid-1;
    }check(l);//!!! l 有可能不等于最后的 mid
    for(int i=1;i<=n;i++) ans-=vis[i];
    printf("%d %d",l,ans);
    return 0;
}