题解：P12545 [UOI 2025] Partitioning into Three

· · 题解

Solve

看到环直接断环为链，因为题目要求三段和于是顺手求前缀和，记 a_{1..n} 的总和为 sum=pre_n。

显然三段和极差最小时，每段的和会尽量接近 \frac{sum}{3}。考虑固定一个切点 x（第一段起点），用双指针找出使第一段和 s_1 最接近 \frac{sum}{3} 的候选边界 y\in[j-1, j]（保持 x<y<x+n-1 且每段非空）。

对每个每个候选的 y，再在区间 [y,x+n-1) 上用二分在前缀和中找使第二段和 s_2 接近剩余的一半（\frac{sum-s_1}2）的两个候选（即 lower_bound 及其前一位）。

计算这至多 4 组 (x,y,z) 的三段和 (s_1,s_2,s_3) 的最大值与最小值之差，取最小者并更新答案。

最后输出三个切点时，只需把在链上的 (x,y,z) 模 n 映射为 [1..n] 内的下标，再排序输出即可（同一组切点的不同起点只是分组名称顺序不同，与答案无关）。

正确性感性理解就行了。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int n,a[N],b[N*2],mx=-1,mn=1e9+1;
ll sum,sumb[N*2],ans=LLONG_MAX;
int ansx,ansy,ansz,p[4];
ll query(int l,int r){
    return sumb[r]-sumb[l-1];
}
void check(int x,int y,int z){
    if(!(x+1<=y && y<=x+n-2)) return;
    if(!(y<=z && z<=x+n-2)) return;
    ll s1=query(x,y-1);
    ll s2=query(y,z);
    ll s3=sum-s1-s2;
    ll mx=max({s1,s2,s3});
    ll mn=min({s1,s2,s3});
    ll diff=mx-mn;
    if(diff<ans){
        ans=diff;
        ansx=x;
        ansy=y;
        ansz=z+1; 
    }
}
int find(int t){
    int r=t%n;
    if(r==0) r=n;
    return r;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    freopen("circle.in","r",stdin);
    freopen("circle.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        b[i]=a[i];
        b[i+n]=a[i];
        sum+=a[i];
        mx=max(mx,a[i]);
        mn=min(mn,a[i]);
    }
    if(n==3){
        cout<<mx-mn<<"\n";
        cout<<1<<" "<<2<<" "<<3;
        return 0;
    }
    for(int i=1;i<=n*2;++i)
        sumb[i]=sumb[i-1]+b[i];
    int j=0;
    for(int x=1;x<=n;++x){
        while(j<x+n-1){//指针j找切点y的边界 
            ll s1=query(x,j-1);
            if(s1*3<sum) ++j;
            else break;         
        }
        vector<int> v;//候选y集合 
        int j1=j-1;
        int j2=min(j,x+n-2);//y不能到x+n-1（否则第二段空）
        if(j1>=x+1) v.push_back(j1);
        if(j2>=x+1){
            if(v.empty() || j2!=v.back())
                v.push_back(j2);
        } 
        for(int y : v){
            ll s1=query(x,y-1);
            ll rem=sum-s1;
            ll t=sumb[y-1]+rem/2;
            //在[y...x+n-2]上找z
            int L=y,R=x+n-1;
            int pos=lower_bound(sumb+L,sumb+R,t)-sumb;
            //候选z：pos与pos-1，均需∈[y...x+n-2] 
            if(pos<x+n-1) check(x,y,pos);
            if(pos-1>=y) check(x,y,pos-1);
        }
    }
    p[1]=find(ansx),p[2]=find(ansy),p[3]=find(ansz);
    sort(p+1,p+1+3);
    cout<<ans<<"\n";
    cout<<p[1]<<" "<<p[2]<<" "<<p[3];
    return 0;
}

枚举 x\in[1...n]，指针 j 单调移动，每个 x 最多二分两次，总复杂度约 O(n\log n)。