[算法入门C5 ] 丢手绢

2023-07-12 00:15 作者:喵雕沙 0人读过 | 我要投稿

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

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

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

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

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

3 1 2 3

3

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

程序

#include <bits/stdc++.h>

using namespace std;

int main() {

int n;

cin >> n;

int all = 0;

int a[n];

for(int i=0;i<n;i++)

{

cin >> a[i];

all += a[i];

}

int sum = 0;

int ans = 0;

for(int i=0, j=0;i<n;i++)

{

while(sum*2<all)

sum += a[j++%n];

ans = max(ans, min(sum, all-sum));

sum -= a[i];

}

cout << ans << endl;

}

标签：

[算法入门C5 ] 丢手绢

题目描述

输入

输出

样例输入复制

样例输出复制

提示