300iq contest1 J. Jealous Split

题意

有一个非负整数序列\({a_i}\)，你要将他分成恰好\(k\)段，记\(s_i\)为第\(i\)段的和，\(m_i\)为第\(i\)段的最大值，你需要保证这种划分方案对任意\(1 \le i < k\)满足:\(|s_i-s_{i+1}|\le \max(m_i,m_{i+1})\)
\(3 \leq k \leq n \leq 100\,000\)
传送门

思路

我们定义“对序列进行一次\(x\)划分”为（从前往后或从后往前）扫一遍序列，每当权值和大于等于\(x\)就分一段。

二分出最大的\(x\)满足划分后段数\(\ge k\)（注意不算最后的和不到的零头段），令其为\(mid\)。

如果对序列进行\(mid\)划分后序列被恰好分成了\(k\)段，那么这种划分方案在原问题下就是最优的且合法的。

若不满足，则可以对序列倒着做\(mid+1\)分段，通过某种方式（这里的证明比较随意，感性理解一下）可以证明正着做\(mid\)分段与倒着做\(mid+1\)分段存在至少一个公共划分点，且满足用前者划分的一段前缀拼上后者划分的一段后缀恰好可以得到原问题的一组合法解。

至于代码那是非常的简短，但是这思路也是神仙了

#include <bits/stdc++.h>
typedef long long ll;
const int N=100005;
int n,a[N],p[N],p2[N],k;
long long l,r,ans;
int check(ll x){
    ll sum=0;int cnt=0;
    for (int i=1;i<=n;i++){
        sum=sum+a[i];
        if (sum>=x) cnt++,sum=0;
    }
    return cnt;
}
int main(){
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]),r=r+a[i];
    while (l<=r){
        ll mid=(l+r)>>1;
        if (check(mid)>=k){
            ans=mid;
            l=mid+1;
        }else r=mid-1;
    }
    puts("Yes");
    ll sum=0;int cnt=0;
    for (int i=1;i<=n;i++){
        sum=sum+a[i];
        if (sum>=ans) p[++cnt]=i,sum=0;
    }
    if (p[cnt]==n && cnt==k){
        for (int i=1;i<cnt;i++) printf("%d ",p[i]);
        puts("");
        return 0;
    }
    sum=0;int cnt2=0;
    for (int i=n;i>=1;i--){
        sum=sum+a[i];
        if (sum>=ans+1) p2[++cnt2]=i,sum=0;
    }
    for (int i=1;i<=cnt;i++){
        if (p[i]==p2[k-i]-1){
            for (int j=1;j<=i;j++) printf("%d ",p[j]);
            for (int j=k-i-1;j>=1;j--) printf("%d ",p2[j]-1);
            puts("");
            break;
        }
    }
    return 0;
}

后记

想不到系列