记录编号	45428	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺十二]圆圈舞蹈	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.147 s
提交时间	2012-10-23 22:06:58	内存使用	4.80 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<deque>
using namespace std;
int n,ww[200005]={0},w[200005]={0},tmp,sum=0,answer=0;
deque<int>q;
int main()
{
	freopen ("circlea.in","r",stdin);
	freopen ("circlea.out","w",stdout);
	scanf("%d",&n);
	for (int i=2;i<=n+1;i++)
	{
		scanf("%d",&tmp);
		ww[i]=tmp;
		ww[i+n]=tmp;
		w[i]=w[i-1]+tmp;
		sum+=tmp;
	}
	for (int i=n+2;i<=2*n+1;i++)
	{
		w[i]=w[i-1]+ww[i];
	}
	sum/=2;
	q.push_back(2);
	for (int i=3;i<=2*n+1;i++)
	{
		while (q.size()&&w[i]-w[q.front()]>sum)
		{
			q.pop_front();
		}
		if (w[i]-w[q.front()]<=sum&&w[i]-w[q.front()]>answer)
			answer=w[i]-w[q.front()];
		q.push_back(i);
	}
	cout<<answer;
	return 0;
}