丢手绢-2020年牛客算法入门课练习赛1

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

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

这显然是个环的问题，还记得环的处理方式吗？没错，就是把数据在数组中存两次就好了。
暴力算法很容易想出来，点i到n+i-1是一个环，用j来循环累加s为i小朋友到j小朋友的顺时针距离，总长度sum-s为逆时针距离，找两者最小值即为i和j的距离，复杂度n^2。
可以看出在处理i时的计算过程在处理i+1时也会重复计算，只是少加了a[i].这类问题可以考虑用two pointer来解决。
i为起点，j为试探点，显然正解只能出现在 i到j距离和sum/2最接近的时候，这个接近可能大，也可能小，所以两种情况都试探下。

#include <bits/stdc++.h>//https://ac.nowcoder.com/acm/contest/5773/C
typedef long long ll;
using namespace std;
ll n,a[200005],sum=0;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    ll i,j,s=0,half,ans=0;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
        a[n+i]=a[i];
        sum+=a[i];
    }
    half=sum/2;
    for(i=1,j=1;i<=n;i++)/**< 一个小朋友是i时，找到和他最远的j */
    {
        while(s<=half) /**< i到j的距离少于一半时，一直求和 */
           s+=a[j++];
        ans=max(ans,min(s-a[j-1],sum-s+a[j-1]));/**< i到j-1小于等于一半 */
        ans=max(ans,min(s,sum-s));/**< i到j大于一半，正解只能是这两者之一 */
        s-=a[i];/**< 下一次处理第i+1个小朋友，先把a[i]拿走 */
    }
    cout<<ans;
    return 0;
}