题目大意：给定一个环，每个人要得到Needi种物品，相邻的人之间不能得到相同的，问至少需要几种。
首先把n=1特判掉。
然后在n为偶数的时候，答案就是max(Needi+Needi+1)(包括(1,n))。
证明：把物品排成一行，只要一个人从左边开始取，下一个人从右边开始取，以此类推，保证不会重复。
然后在n为奇数的时候，答案就不好做了。
观察一下这道题，发现答案满足可二分性，不如思考一下check怎么写。
因为n为奇数时难点就在看n与1是否矛盾上，只要解决了这个问题，一切好说。
不难发现答案下界就是max(Needi+Needi+1)(包括(1,n))，上界开大一点无所谓的。
还是把物品排成一行，第一个人从左边开始取。
要使第n个人和第1个人尽量不矛盾，不如让他从最后开始选。
然后n-1就从前面开始选。
一路逆推回来，你会发现：让2从左边开始选。
什么？1不是从左边开始选的吗？为什么2也从左边开始选呢？
因为我们二分的mid是可以保证(i,i+1)之间一定不矛盾的，所以从2开始做就是为了n号点与1号点的尽量不矛盾。
换句话说，不会转过圈的都是一定满足的，所以就是要把它们以一种合适的方式排布，成全n和1这一对。
感觉在下一盘惊天大棋？
至于维护方式，也是比较巧(套)妙(路)的。
有mid个物品，第一个人选了前Need[1]个，我们就把这些物品分成左右，[1,Need[1]]和[Need[1]+1,mid]。
记L[i]和R[i]表示i在左边/右边取了多少个。
对于偶数位，由推导，我们尽量从左边选。
L[i]=min(Need[i],Need[1]-L[i-1]),R[i]=Need[i]-L[i]。
对于奇数位，尽量从右边选。
R[i]=min(Need[i],(mid-Need[1])-R[i-1]),L[i]=Need[i]-R[i]。
最后，因为1把L全部取完了，我们只要看L[n]==0即可。
真是妙。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <complex>
#include <stack>
#define LL long long int
#define dob double
#define FILE "3177"
using namespace std; const int N = ;
int n,Ned[N],L[N],R[N]; inline int gi(){
int x=,res=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')res*=-;ch=getchar();}
while(ch<=''&&ch>='')x=x*+ch-,ch=getchar();
return x*res;
} inline bool check(int mid){
int Lh=Ned[],Rh=mid-Ned[];
L[]=Lh;R[]=;
for(int i=;i<=n;++i)
if(i&){
R[i]=min(Ned[i],Rh-R[i-]);
L[i]=Ned[i]-R[i];
}
else{
L[i]=min(Ned[i],Lh-L[i-]);
R[i]=Ned[i]-L[i];
}
return L[n]==;
} int main()
{
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
while(n=gi()){
for(int i=;i<=n;++i)Ned[i]=gi();
if(n==){printf("%d\n",Ned[]);continue;}
int Ans=Ned[n]+Ned[];
for(int i=;i<n;++i)
Ans=max(Ans,Ned[i]+Ned[i+]);
if(n&){
int l=Ans,r=Ans*;Ans=r;
while(l<=r){
int mid=(l+r)>>;
if(check(mid))r=mid-,Ans=mid;
else l=mid+;
}
}
printf("%d\n",Ans);
}
fclose(stdin);fclose(stdout);
return ;
}
Beijing Guards