题解 | #丢手绢#

链接：https://ac.nowcoder.com/acm/problem/207040

来源：牛客网

题目描述

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

尺取法

用黑线画出小朋友们围成的圈，先计算出圈的总长度sum，对于任意小朋友（最上面的小黑圈）让右指针r从他出发顺时针走并记录经过的路程s，当s >= sum - s时，到达关键位置，此时他与其他小朋友离得最远的距离应该是sum - s与s - a[ r ]中更长的那个，用结果更新答案ans并使左指针 l 前移一步，寻找下一个小朋友的最长距离（记得s - a[ l ]），r走完所有小朋友即结束

using namespace std;

int main(){
    // n为输入的距离数量 sum为总距离之和
    int n, sum = 0;
    cin >> n;
    int a[n];

    for(int i = 0; i < n; i++){
        cin >> a[i];
        sum += a[i];
    }

    // l, r为左右指针 s为l与r之间距离总和 ans为离得最远的两个小朋友之间的距离
    int l = -1, r = -1, s = 0, ans = 0;
    while(r < n){
        if(s < sum - s){
            s += a[++r];
        }else{
            ans = max(ans, max(sum - s, s - a[r]));
            s -= a[++l];
        }
    }
    cout << ans << endl;
}