【问题描述】
熊大妈的奶牛在时针的带领下，围成了一个圈跳舞。由于没有严格的教育，奶牛们之间的间隔不一致。奶牛想知道两只最远的奶牛到底隔了多远。奶牛A 到B 的距离为A 顺时针走和逆时针走，到达B 的较短路程。告诉你相邻个奶牛间的距离，请你告诉奶牛两只最远的奶牛到底隔了多远。
【输入格式】
第一行一个整数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
【样例解析】
所有奶牛I 到J 之间的距离和到达方式（顺为顺时针，逆为逆时针）如下
IJ 1 2 3 4 5
1 0 1(顺) 3（顺） 6（顺） 5（逆）
2 1（逆） 0 2（顺） 5（顺） 6（逆）
3 3（逆） 2（逆） 0 3（顺） 7（顺）
4 6（逆） 5（逆） 3（逆） 0 4（顺）
5 5（顺） 6（顺） 7（逆） 4（逆） 0
所以，最远的两头奶牛为3 到5，距离是7。
朴素的算法就是全部枚举，时间复杂度能达到O(n ^ 3)，若用前缀和优化距离，就能达到O(n ^ 2)。而且还有一个小优化，因为是顺逆时针走所以2到5的距离就是5到2的距离，这就不用重复枚举了，复杂度达到O(n * (n - 1) / 2)，但其实本质上并没有多大进步。
其实我们发现答案肯定是整个周长的一半左右，所以我们可以枚举每一个点，然后直接找到第一个累积和大于半周长的点，然后和总周长减去刚才找到的长度 进行比大小，根据题目要求是两者取小的，然后更新答案。
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 using namespace std; 7 typedef long long ll; 8 const int maxn = 1e5 + 5; 9 int n, a[maxn], k; 10 ll total = 0, sum = 0, ans = 0; 11 int main() 12 { 13 freopen("circle.in","r",stdin); 14 freopen("circle.out","w",stdout); 15 scanf("%d", &n); 16 for(int i = 1; i <= n; ++i) {scanf("%d", &a[i]); total += a[i];} 17 for(int i = 1; i <= n; ++i) 18 { 19 sum += a[i - 1]; 20 if(sum > total / 2) { k = i; break;} 21 } 22 ans = max(ans, min(sum, total - sum)); 23 ans = max(ans, min(sum - a[k - 1], total - (sum - a[k - 1]))); 24 for(int i = 2; i <= n; ++i) 25 { 26 sum -= a[i - 1]; 27 while(sum <= total / 2) {sum += a[k + 1]; k++;} 28 ans = max(ans, min(sum, total - sum)); 29 ans = max(ans, min(sum - a[k - 1], total - (sum - a[k - 1]))); 30 } 31 printf("%d", ans); 32 return 0; 33 }