记录编号	328983	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺十二]圆圈舞蹈	最终得分	100
用户昵称	Smile	是否通过	通过
代码语言	C++	运行时间	0.206 s
提交时间	2016-10-24 19:28:04	内存使用	1.07 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn=100000+10;
const int INF=0x3f3f3f3f;

int a[maxn], H[maxn], n;
int ans=0, sum=0;

void init()
{
	scanf("%d", &n);
	for(int i=1; i<=n; i++) scanf("%d", &a[i]), sum+=a[i];
	for(int i=2; i<=n; i++) H[i]=H[i-1]+a[i-1];
}

void work()
{
	for(int i=1; i<=n/2; i++) {
		int L, R, cnt=0;
		L=R=i+(n/2);
		if(L>n) L=R=L%n;
		int s1=H[L]-H[i];
		int s2=sum-s1;
		cnt=min(s1, s2);
		L--; R++;
		while(L!=i) {
			int s1=H[L]-H[i];
			int s2=sum-s1;
			if(cnt>min(s1, s2)) break;
			cnt=min(s1, s2);
			L--;
		}
		if(R>n) R=R%n;
		while(R!=i) {
			int s1=H[R]-H[i];
			int s2=sum-s1;
			if(cnt>min(s1, s2)) break;
			cnt=min(s1, s2);
			R++;
			if(R>n) R=R%n;
		}
		ans=max(ans, cnt);
	}
	for(int i=n/2+1; i<=n; i++) {
		int L, R, cnt=0;
		L=R=i+n/2;
		if(L>n) L=R=L%n;
		int s1=H[i]-H[L];
		int s2=sum-s1;
		cnt=min(s1, s2);
		L--; R++;
		if(L==0) L=n;
		while(L!=i) {
			int s1, s2;
			if(i>L) s1=H[i]-H[L];
			else s1=H[L]-H[i];
			s2=sum-s1;
			if(cnt>min(s1, s2)) break;
			cnt=min(s1, s2);
			L--;
			if(L==0) L=n;
		}
		while(R!=i) {
			int s1=H[i]-H[R];
			int s2=sum-s1;
			if(cnt>min(s1, s2)) break;
			cnt=min(s1, s2);
			R++;
		}
		ans=max(ans, cnt);
	}
	printf("%d", ans);
}

int main()
{
	freopen("circlea.in", "r", stdin);
	freopen("circlea.out", "w", stdout);
	init();
	work();
	return 0;
}