自动搬运

查看原文

来自洛谷，原作者为

	Wenoide Wrong answer on line 1 column 12.

搬运于2025-08-24 22:21:21，当前版本为作者最后更新于2020-05-10 20:18:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

重复下述步骤：

• 若最左端元素较最右端元素更小，则合并最左端的两个元素。
• 若最右端元素较最左端元素更小，则合并最右端的两个元素。
• 若两端的元素相等，则对除两端的元素外的其他元素重复以上步骤。

显然，回文数组两端的元素应相等。

第一种情况下，迟早需要合并最左端的两个元素。否则最右端的元素会越来越大，直到数组中只剩一个元素。

第二种情况同理。

第三种情况下，两端的元素已经回文，可以不作处理。

时间复杂度 $O(n)$。

参考代码：

#include<cstdio>
const int MAXN=1000000+10;
long long p[MAXN];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%lld",&p[i]);
	}
	int l=1,r=n,cnt=0;
	while(l<r){
		if(p[l]>p[r]){
			--r;
			p[r]+=p[r+1];
			++cnt;
		}
		else if(p[l]<p[r]){
			++l;
			p[l]+=p[l-1];
			++cnt;
		}
		else{
			++l,--r;
		}
	}
	printf("%d",cnt);
	return 0;
}