自动搬运

查看原文

来自洛谷，原作者为

	Math_rad_round 旋转卡壳有2^4种读法，你知道吗？||NOIP退役苕皮

搬运于2025-08-24 22:15:50，当前版本为作者最后更新于2021-10-12 21:04:41，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题面

简要题意：在一个环形数列中选择连续的若干个数，使得【这些数的和】与【其他数的和】的最小值最大。

我们可以枚举我们选一串数的终点在哪里，显然，为了让这串数的和是答案，它的和不能超过数列总和的一半，同时我们要让这个和尽量大。所以我们要贪心的往前选择，这样就达到了 $O(n^2)$ 的复杂度

如何优化呢？我们可以发现当终向后时，起点也一定是随着向后。所以我们当从一个终点转到下一个终点时，我们要判断现在总长是否超过要求，如果是，我们就贪心的把起点一位一位往后移动。

那么我们要怎样处理这个环呢？对于环上问题，我们最常用的方式就是把整段序列复制一次接到后面，这样我们就可以方便的处理经过 $len_n$ 和 $len_1$ 的区间了。

AC代码

#include<iostream>
using namespace std;
int len[1000000];
int sum=0;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>len[i];sum+=len[i];
		len[i+n]=len[i];
	}
	int ans=0,maxl=sum/2+1;//答案，最大答案。 
	int now=0,qi=1;//当前长度，当前的起点 
	for(int i=1;i<=2*n;i++){
		now+=len[i];
		while(now>=maxl){
			now-=len[qi];qi++;		
		}
		ans=max(now,ans);
	}
	cout<<ans;
	return 0;
}