题解 | #丢手绢#

题意 n个人围成一圈，两个人的距离为顺时针和逆时针距离较短的那个，求两个人的最长距离
解法一 对于每个人来说，考虑哪个人离他最远，容易想到在sum[n]附近，所以可以二分找左右的3个人，复杂度nlongn
解法二 尺取 和二分思路差不多 但是复杂度更低 i j遍历n就可

#include<iostream>
using namespace std;
int n,a[100010],sum[100010];
int main()
{
    int ans=0,now=0;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],sum[i]=sum[i-1]+a[i];
    for(int i=1,j=1;i<=n;i++)
    {
        while(j<=n&&now<sum[n]/2)
        {
            now+=a[j];
            ans=max(ans,min(sum[j]-sum[i-1],sum[n]-sum[j]+sum[i-1]));
            j++;
        }
        now-=a[i];
    }
    cout<<ans<<endl;
}