输入描述:

第一行一个整数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
来源：牛客网