题解 | #丢手绢#
丢手绢
https://ac.nowcoder.com/acm/problem/207040
链接：https://ac.nowcoder.com/acm/problem/207040
来源：牛客网
来源：牛客网
题目描述
“丢~丢~丢手绢，轻轻地放在小朋友的后面，大家不要告诉她，快点快点抓住她，快点快点抓住她。”
牛客幼儿园的小朋友们围成了一个圆圈准备玩丢手绢的游戏，但是小朋友们太小了，不能围成一个均匀的圆圈，即每个小朋友的间隔可能会不一致。为了大家能够愉快的玩耍，我们需要知道离得最远的两个小朋友离得有多远（如果太远的话牛老师就要来帮忙调整队形啦！）。
因为是玩丢手绢，所以小朋友只能沿着圆圈外围跑，所以我们定义两个小朋友的距离为沿着圆圈顺时针走或者逆时针走的最近距离。
本题使用双指针的做法去求解（尺取法）。创建一个i和一个j,i是进的那一个，j是远的那一个。在i和j之间的距离大于或等于这个圆的周长的一半的时候长度达到最大。当进入到下一个i的时候这个时候的j要么是最大的要么还需要向前进一位。所以比起双重循环遍历节省了许多时间。
#include <iostream>
#include <cstdio>
#include <limits.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int main() {
IOS;
int n, sum = 0;
cin>>n;
int a[n];
for (int i=0;i<n;i++) {
cin>>a[i];
sum += a[i];
}
int len = 0, res = INT_MIN;
int j = 0, cnt = 0;
for (int i=0;i<n;i++) {
while (cnt<sum/2) {
cnt+=a[j%(n)];
j++;
}
res = max(res, min(cnt, sum-cnt));
cnt-=a[i];
}
cout<<res;
return 0;
}
