“丢~丢~丢手绢，轻轻地放在小朋友的后面，大家不要告诉她，快点快点抓住她，快点快点抓住她。” 牛客幼儿园的小朋友们围成了一个圆圈准备玩丢手绢的游戏，但是小朋友们太小了，不能围成一个均匀的圆圈，即每个小朋友的间隔可能会不一致。为了大家能够愉快的玩耍，我们需要知道离得最远的两个小朋友离得有多远（如果太远的话牛老师就要来帮忙调整队形啦！）。 因为是玩丢手绢，所以小朋友只能沿着圆圈外围跑，所以我们定义两个小朋友的距离为沿着圆圈顺时针走或者逆时针走的最近距离。

输入描述:

第一行一个整数N，表示有N个小朋友玩丢手绢的游戏。
接下来的第2到第n行，第i行有一个整数，表示第i-1个小朋友顺时针到第i个小朋友的距离。
最后一行是第N个小朋友顺时针到第一个小朋友的距离。

输出描述:

输出一个整数，为离得最远的两个小朋友的距离。

分析

对于围成的圆圈，最长的距离就是直径上两端点的距离，因此两个小朋友的距离要尽可能远。只需要枚举每一个小朋友，然后找到与他在同一直径上的小朋友。
具体使用尺取法，尺内大小保持一半的周长。枚举每一个小朋友确定第一个端点，移动右指针，当距离达到或大于一半周长时，即找到与他在同一直径上的小朋友。根据题意，取顺时针或逆时针最小的一个更新当前最大值，然后移动左指针。需要的注意的是圆圈是环，右指针达到N时置重新最开始位置

AC

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        int[] arr = new int[N];
        int sum = 0;
        for(int i = 0; i < N; ++i) {
            arr[i] = Integer.parseInt(bf.readLine());
            sum += arr[i];
        }
        final int half = sum / 2;
        int max = Integer.MIN_VALUE;
        int i = 0, j = 0, cur = 0;
        while(i < N) {
            while(true) {
                cur += arr[j];
                if(cur >= half) {
                    max = Math.max(max, Math.min(cur, sum - cur));
                    cur -= arr[i++];//移动左指针
                    cur -= arr[j];//多加了一次，需要减掉
                    break;
                } else {
                    if(++j == N)
                        j = 0;
                }
            }
        }
        System.out.println(max);
	} 
}

链接：https://ac.nowcoder.com/acm/contest/20960/1030
来源：牛客网