[NC207040] 丢手绢

题目描述

“丢~丢~丢手绢，轻轻地放在小朋友的后面，大家不要告诉她，快点快点抓住她，快点快点抓住她。”

牛客幼儿园的小朋友们围成了一个圆圈准备玩丢手绢的游戏，但是小朋友们太小了，不能围成一个均匀的圆圈，即每个小朋友的间隔可能会不一致。为了大家能够愉快的玩耍，我们需要知道离得最远的两个小朋友离得有多远（如果太远的话牛老师就要来帮忙调整队形啦！）。

因为是玩丢手绢，所以小朋友只能沿着圆圈外围跑，所以我们定义两个小朋友的距离为沿着圆圈顺时针走或者逆时针走的最近距离。

输入描述:

第一行一个整数 $N$，表示有 $N$ 个小朋友玩丢手绢的游戏。
接下来的第 $2$ 到第 $n$ 行，第 $i$ 行有一个整数，表示第 $i-1$ 个小朋友顺时针到第 $i$ 个小朋友的距离。
最后一行是第 $N$ 个小朋友顺时针到第一个小朋友的距离。

输出描述:

输出一个整数，为离得最远的两个小朋友的距离。

输入

1
2
3
4
3
1
2
3

输出

1
3

备注:

$2≤N≤100000$
距离和（圆圈周长）小于等于 $2147483647$

题解

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>

using namespace std;
const int MAX = 100000+10;

int p[MAX];

int main(){
    int n,sum=0,ans=0;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> p[i];
        sum += p[i];
    }
    int l=0,r=0,sums=0;
    while(l<n){
        for(;p[r]+sums<=(sum>>1);r=(r+1)%n){ //  [1]
            sums += p[r];
        }
        ans = max(ans,sums);
        sums -= p[l];
        l++;
    }
    cout << ans;
    return 0;
}

解析

  • 用到了尺取法的思想,R指针始终不会后退,只有L指针不断往后移动,而且 $sum(L \to R)$ 必须要小于 $SUM>>1$ 这样可以防止重复计算.
  • 又是刷题的一天
    • 卡在了一个奇奇怪怪的地方: 忘了咋给 $r$ 递增了看了看别的代码,别人用了 $[1]$ 我才想起来能用 $for$ = =.
    • 我好菜.