题解：P12545 [UOI 2025] Partitioning into Three

Comentropy · 2025-06-25 10:30:33 · 题解

不错的题。研究环状序列的分割，使用经典套路：把序列复制一份接在后面，对新序列的每个长为 n 的区间做。很容易能说明所有分段方案都必然存在一个在新序列上的映射。

方便刻画区间和，先把序列前缀和，让 s_i 表示 [1,i] 的和。

我们要把序列分成三段 [i,j],[j+1,k],[k+1,i+n-1]，记 R=i+n-1。从小到大枚举 i，并考虑钦定一个这些段内和之间的大小关系。从左到右依次标号这些段，假设我们是要 g_1\geq g_2\geq g_3。

于是我们有如下限制（简洁起见，跳了一步列式）：

理一个关于 s_k 的式子，关注 s_j 和 s_k 的关系：

而我们要最小化：

其中 s_{i-1}+s_{i+n} 已经确定，我们要最小化的就是 s_j+s_k。由于 a_i 非负，所以 s_i 单增，我们要让 j,k 尽可能靠前。不难发现这个限制是统一的，即 i,j,k 三个指针在过程中的移动是统一的（单增）：

假设我们暴力从小到大枚举 j，此时 s_k 的下界不断提升，则可能的 k 在不断向后，当刚好存在在限制区间内的 s_k 的时候，这个最小的 k 就是我们要找的。加入对 i 的考虑：在 i 不断变大的过程中，对于相同的 j，对 s_k 的限制下界变大，上界变小，则更难以存在合法的 k。

于是我们就说明了三个指针移动方向的统一性。

最后，事实是，我们只需要钦定两次这样的大小关系，在环状序列上划分三段的大小关系本质只有两种：g_1\geq g_2\geq g_3 以及 g_1\leq g_2\leq g_3。所以，你可以直接把序列 reverse 再做一遍，即可。时间复杂度 O(n)。

在感冒，代码里的细节理了一会儿，不过不算难写。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=2e6+10;
const LL INF=1e18;
int n,a[N];
LL s[N];
array<LL,4> ans={INF,0,0,0};
inline LL rsum(int i,int j){
    return s[j]-s[i-1];
}
void solve(int rev){    
    for(int i=1;i<=n*2;i++)
        s[i]=s[i-1]+a[i];
    auto turn=[&](LL x){
        if(rev) x=n*2-(x-1)+1;    // 从区间的另一侧起点做——也就是自己先减 1 再倒过来。
        return x%n==0?n:x%n;
    };
    for(int i=1,j=0,k=0,R=n;i<=n;i++,R++){
        j=max(j,i);
        while(j+1<R){
            for(k=max(j+1,k);k<R && rsum(j+1,k)<rsum(k+1,R);k++);
            if(k+1<=R && rsum(i,j)>=rsum(j+1,k) && rsum(j+1,k)>=rsum(k+1,R)){
                ans=min(ans,{rsum(i,j)-rsum(k+1,R),turn(i),turn(j+1),turn(k+1)});
                break ;
            }
            j++;
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),a[i+n]=a[i];

    solve(0);
    reverse(a+1,a+1+2*n);
    solve(1);

    sort(ans.begin()+1,ans.end());
    printf("%lld\n%lld %lld %lld\n",ans[0],ans[1],ans[2],ans[3]);
    return 0;
}