题解 | #丢手绢#

这道题求一个环中两点距离的(优弧)最大值,显然这个最大值是不会超过圆环周长的一半的

所以大概的做法是(尺取法):

先求出圆环的周长的一半,从一点开始向后计算距离,如果距离>=周长的一半说明当前点就是到起始点距离最远的点 但是这个距离要是是优弧:即从起始点两个方向到当前点的距离中较小的那个.

然后以同样方式继续

Java AC代码:

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[2 * n];
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            a[i] = in.nextInt();
            sum += a[i];
        }
        int h = sum / 2;
        int res = 0, l = 0, r = 0, len = 0;
        while (l < n) {// 左边界到达终点才算所有的点都计算完成
            while (len < h)// 距离未到最大
                len += a[r++ % n];// 在数组内循环
            if (len == h)// len是l到r的最大距离
                res = Math.max(res, len);
            else if (len > h)// sum-len是l到r的最大距离
                res = Math.max(res, sum - len);
            len -= a[l++];
        }
        System.out.println(res);
    }
}