自动搬运

查看原文

来自洛谷，原作者为

	lam_dyr 少年曾许凌云志，誓做天下第一流

搬运于2025-08-24 23:16:22，当前版本为作者最后更新于2025-08-13 16:36:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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)$。