题解 | #丢手绢#

一道很有意思的题目，考察的基础知识较多。首先处理最极限的情况——圆的顺时针或者逆时针的长度是一样的。这是我们的边界条件叫他ave,决定他是一条优弧还是劣弧(由于取最短距离，所以本题的答案，必须要取劣弧进行比较)，利用双指针思想，不断扩大区间长度，直到长度到了ave。

** sum1 += a[(j++)%N]**

和这种while (sum1<ave&&j<=N)的区别是什么?

举个例子--J=N+1;下面的代码无法进行，而上面的重新回到了第一位，即完成了环状访问。

要注意的地方就是双指针的合法区间标准和完成一个环状访问，最后附上ac代码

#include

using namespace std;

int a[100000];

int main()

{

int N, sum, ans;

cin >> N;
sum = 0;
for (int i = 0;i < N;i++)
{
    cin >> a[i];
    sum += a[i];
}
//顺时针或者逆时针的最近距离，不妨假设两个的距离相等，就可以找到边界(特殊情况),就是周长的一半
int ave = sum / 2;
int sum1 = 0;
ans = 0;
int j = 0;
for (int i= 0;i < N;i++)
{
    while (sum1 < ave)
    {
        sum1 += a[(j++)%N];//模拟环状访问
    }
    ans = max(ans, min(sum1,sum-sum1));
    //这里是为了洗去边界值，要判断下一个区间前必须洗去上一组数据
    sum1 -= a[i];

}
cout << ans;

}

注，本人在做题的时候还发现了一种很巧妙的思路，即下面这种代码

#include

using namespace std;

int a[100000];

int main()

{

int N,sum;
cin >> N;
sum=0;
for (int i = 0;i < N;i++)
{
    cin >> a[i];
    sum+=a[i];
}
int ave=sum/2;
cout<<ave;

} 他只有80%的通过率，我查出来是如果是一个均匀的圆是错误的，如果进行分类讨论或许有新的题解