题目：Beijing Guards
思路：
令 a[n+1] = a[n] 。
如果n为偶数，答案为相邻两数和的最大值。
如果n为奇数，二分。
注意：n为1时要单独考虑。
代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <cstring>
#include <map>
#include <cmath>
using namespace std;#define maxn 100000int n;
int a[maxn+5];int Even(){int s=0;for(int i=1;i<=n;i++){s=max(s,a[i]+a[i+1]);}return s;
}bool judge(int x){int frt[maxn+5],bhd[maxn+5];frt[1]=a[1],bhd[1]=0;for(int i=2;i<=n;i++){if(i&1){bhd[i]=min(x-a[1]-bhd[i-1],a[i]);frt[i]=a[i]-bhd[i];}else{frt[i]=min(a[1]-frt[i-1],a[i]);bhd[i]=a[i]-frt[i];}}if(frt[n]) return false;return true;
}int Odd(){int l=Even(),r=0;for(int i=1;i<=n;i++) r=max(r,a[i]*3);while(l<r){int mid=(l+r)/2;if(judge(mid)) r=mid;else l=mid+1;}if(!judge(l+1)) l++;return l;
}int main() {while(~scanf("%d",&n)&&n){for(int i=1;i<=n;i++){scanf("%d",&a[i]);}a[n+1]=a[1];if(n==1) printf("%d\n",a[1]);else if(n&1){ //奇数 printf("%d\n",Odd());} else { //偶数 printf("%d\n",Even());}}return 0;
}