题解 | #丢手绢#

尺取法是一种双指针算法，通常用于解决一些区间问题。它的基本思想是维护一个区间，然后通过移动左右指针来调整区间的大小和位置，以便找到符合条件的解。在这个问题中，我们需要找到离得最远的两个小朋友之间的距离。我们可以使用尺取法来解决这个问题。具体来说，我们可以使用两个指针i和j来表示当前考虑的两个小朋友之间的距离。我们可以让指针i从0开始遍历数组，并让指针j从i开始向右移动，直到找到一个位置k，使得从i到k和从k到i+n（n是数组长度）之间的距离最大。然后，我们可以更新答案，并将指针i向右移动一位。重复这个过程直到遍历完整个数组。

这道题的思路很明显用双指针来做。(核心是判断指针r是否需要复位来判断是否是尺取法)。

细节 cnt+=a[(j++)%n];

这行代码是尺取法的核心部分。它使用了双指针技巧来找到两个子数组，使它们的元素和最接近数组元素和的一半。具体来说，它使用了一个循环来不断增加cnt的值，直到cnt大于等于数组元素和的一半。然后，它使用while循环来不断减少cnt的值，直到cnt小于数组元素和的一半。在这个过程中，j指针会不断向右移动，并使用模运算来保证它不会超出数组范围。当cnt大于等于数组元素和的一半时，我们就可以计算出当前两个子数组元素和之间的差值，并将其与之前计算出的差值进行比较，从而找到最小值。

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int a[N];
int sum;

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    int x=sum/2;
    int res=0;
    int cnt=0;
    int j=0;
    for(int i=0;i<n;i++)
    {
        while(cnt<x)
        {
            cnt+=a[(j++)%n];
        }
        res=max(res,min(cnt,sum-cnt));
        cnt-=a[i];
    }
    cout<<res<<endl;

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N];
int main()
{
    cin>>n;
    int sum = 0;
    for(int i = 0; i < n; i++)
    {
        cin>>a[i];
        sum += a[i];
    }
    int r = -1;
    int cnt = 0, res = 0;
    for(int l = 0; l < n; l++)
    {
        while(cnt < sum/2)
        {
            r++;
            cnt += a[r%n];
        }
        res = max(res, min(cnt, sum - cnt));
        //l移动
        cnt -= a[l];
    }
    cout << res << endl;
    
    return 0;
}