记录编号	45452	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺十二]圆圈舞蹈	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.182 s
提交时间	2012-10-24 07:35:19	内存使用	3.52 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
 
long long zc,maxdis,maxpos=2,temp,temp2,s[100010];
 
int main(void)
{
	freopen("circlea.in","r",stdin);
	freopen("circlea.out","w",stdout);
	int i,n;
	cin>>n;
	for (i=1;i<=n;i++)
		cin>>s[i];
	for (i=1;i<=n;i++)
		s[i]=s[i-1]+s[i];
	zc=s[n];
	s[0]=s[n];
	s[n+1]=s[1];
	for (i=1;i<=n;i++)
	{
		temp=abs(s[maxpos]-s[i]);
		temp2=zc-temp;
		while (temp2>temp)
		{
			maxpos++;
			if (maxpos>n)
				maxpos=1;
			if (maxpos==i)
			{
				temp2=0;
				break;
			}
			temp=abs(s[maxpos]-s[i]);
			temp2=zc-temp;
		}
		temp=abs(s[maxpos-1]-s[i]);
		if (temp>temp2)
		{
			if (temp>maxdis)
				maxdis=temp;
			maxpos--;
			if (maxpos<1)
				maxpos=n;
		}
		else
		{
			if (temp2>maxdis)
				maxdis=temp2;
//			maxpos=maxpos;
		}
	}
	cout<<maxdis<<endl;
	return(0);
}