[算法入門C5 ] 丟手絹
題目描述
“丟~丟~丟手絹，輕輕地放在小朋友的后面，大家不要告訴她，快點快點抓住她，快點快點抓住她?！?br>
幼兒園的小朋友們圍成了一個圓圈準備玩丟手絹的游戲，但是小朋友們太小了，不能圍成一個均勻的圓圈，即每個小朋友的間隔可能會不一致。為了大家能夠愉快的玩耍，我們需要知道離得最遠的兩個小朋友離得有多遠（如果太遠的話老師就要來幫忙調(diào)整隊形啦?。?/p>
因為是玩丟手絹，所以小朋友只能沿著圓圈外圍跑，所以我們定義兩個小朋友的距離為沿著圓圈順時針走或者逆時針走的最近距離。
輸入
第一行一個整數(shù)N，表示有N個小朋友玩丟手絹的游戲。
接下來的第2到第n行，第i行有一個整數(shù)，表示第i-1個小朋友順時針到第i個小朋友的距離。
最后一行是第N個小朋友順時針到第一個小朋友的距離
輸出
輸出一個整數(shù)，為離得最遠的兩個小朋友的距離
樣例輸入?復(fù)制
3
1
2
3
樣例輸出?復(fù)制
3
提示
2≤N≤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;}標簽：
