【问题描述】
露娜代替羚羊夫人带领佩奇、乔治、苏西等小朋友围成一圈跳舞。由于小朋友们的年龄太小了，它们之间的间隔不一致。
佩奇想知道两个最远的小朋友到底隔了多远。举个栗子，佩奇到苏西的距离为佩奇顺时针走和逆时针走，到达苏西的较短路程。告诉你相邻两个小朋友间的距离，请你告诉佩奇两只最远的小朋友到底隔了多远。
【输入格式】
第一行一个整数N，表示有N个小朋友（2<=N<=100000）
接下来2~N+1行，第I行有一个数，表示第I-1个小朋友顺时针到第I个小朋友的距离（1<=距离<=maxlongint,距离和<=maxlongint）
第N+1行的数表示第N个小朋友顺时针到第1小朋友的距离
【输出格式】
一行，表示最大距离
【输入样例】circle.in
5
1
2
3
4
5
【输出样例】Circle.out
7
【样例解析】
【胡乱分析】
先选定一个小朋友A，找到离他最远的小朋友C，计算两者的距离。那么它的离他下一个小朋友B最远的小朋友D一定在C的后面，不可能在C的前面。因此只要找到A的最远小朋友，再从C的下一个开始找B的最远小朋友，相当于两个指针分别走了一圈，时间复杂度降低为O（n）
【代码参考】
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 using namespace std; 7 int main() 8 { 9 int n,tall[100005],sum = 0,k = 0,a,ans = 0; 10 scanf("%d",&n); 11 for(int i = 1;i <= n;i++) 12 { 13 scanf("%d",&tall[i]); 14 sum+=tall[i];//计算总距离 15 } 16 for(int i = 1;i <= n;i++)//枚举第一个小朋友与跟它最远的小朋友的距离 17 { 18 k+=tall[i]; //记录小朋友与第一个小朋友的距离 19 if(k >= sum / 2)break;//距离大于总距离的一半，已经到了最远点附近，退出循环 20 a = i;//记录当前位置 21 } 22 ans = max(ans,min(k,sum-k)); 23 ans = max(ans,min(k - tall[a-1],sum-(k-tall[a-1])));//求出最终的最远距离 24 for(int i = 2;i <= n;i++)//开始从第二个小朋友枚举 25 { 26 k-=tall[a-1]; //删去前一个小朋友的距离 27 while(k <= sum / 2) 28 { 29 k+=tall[a+1]; 30 a++; 31 } 32 ans = max(ans,min(k,sum-k)); 33 ans = max(ans,min(k-tall[a-1],sum-(k-tall[a-1])));//更新最远距离 34 } 35 printf("%d",ans); 36 return 0; 37 }
.至于代码中ans算了两边，可以看做一个时钟，要计算12点到谁的距离最远，但是小朋友的位置恰好分布在6点的左右两边且距离不等，此时他俩都有可能是距离12点最远的。这时，6点左边的小朋友有一个顺时针和一个逆时针的距离，6点右边的小朋友也有。分别求出四个距离，比较出最大的那个，才能确定最终离12点最远的。