P2381 圆圆舞蹈
题目描述
熊大妈的乃修在时针的带领下，围成了一个圆圈舞蹈，由于没有严格的教育，奶牛们之间的间隔不一致。
奶牛想知道两只最远的奶牛到底隔了多远。奶牛A到B的距离为A顺时针走和逆时针走，到达B的较短路程。告诉你相邻两个奶牛件的距离，请你告诉奶牛两只最远的奶牛到底隔了多远。
输入输出格式
输入格式：
第一行一个整数N，表示有N只奶牛。（2<=N<=100000）
接下2-N+1行，第i行有一个数，表示第i-1头奶牛顺时针到第i头奶牛的距离。（1<=距离<=maxlingint,距离和<=maxlongint）
第N+1行的数表示第N头奶牛顺时针到第1头奶牛的距离。
输出格式：
一行，表示最大距离。
输入输出样例
输入样例#1：
Crile.in 5 1 2 3 4 5
输出样例#1：
Crile.out 7
二分答案
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 200010
using namespace std;
int ans,n,m,q,w,x,y,l,r,mid,sum[N],minn;
int read()
{
,f=; char ch=getchar();
;ch=getchar();}
+ch-',ch=getchar();
return x*f;
}
int main()
{
n=read();
;i<=n+;i++)
{
x=read();q+=x;
sum[i]=sum[i-]+x;
}
;i<=*n;i++)
sum[i]=sum[i-n]+q;
;i<=n;i++)
{
l=i,r=n+i;
minn=<<-;
while(l<=r)
{
mid=(l+r)>>;
x=sum[mid]-sum[i];
y=sum[n+i]-sum[mid];
if(abs(x-y)>minn)
{
minn=abs(x-y);
w=min(x,y);
if(ans<w) ans=w;
}
if(l==mid) break;
if(x<y) l=mid;
else r=mid;
}
x=sum[r]-sum[i];
y=sum[n+i]-sum[r];
if (abs(x-y)<minn)
{
minn=abs(x-y);
w=min(x,y);
if(w>ans) ans=w;
}
}
printf("%d",ans);
;
}