UVALLive 3177-欲張り+二分

http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18523
标题:n人が一回りしていて、i人目はtm[i]個の異なる贈り物が必要で、隣接する2人は同じ種類の贈り物を持つことができなくて、n人目と1人目は隣接しています
最低何種類の贈り物が要求を満たすことができるかを聞きます (贈り物の数は無限で、繰り返し使用できます)
nが偶数の場合は最大max(tm[i]+tm[i+1])を1つだけ求める必要がある. 明らかに奇数の人選の前の部分、偶数の人選の後ろの部分、永遠に繰り返すことはありません
nが奇数の場合、上記の方法でも、1人目とn人目が奇数で、重複するものを選ぶ可能性があります.では、n-1人目(番号は偶数)で選んだ贈り物の種類をできるだけ1人目と同じにし、隣接していないので、できるだけ同じにする必要があります.n番目の人はn番目の人と衝突しないようにもっと多くの贈り物を選ぶことができます. また1人目と衝突しなくなった...
このように選択されたスキームは明らかに最初の人選1からtm[1]であり、その後の 偶数の人はできるだけ左、奇数の人はできるだけ右、   n-1人目のプレゼントIDをできるだけ左(つまり1人目と同じ)に近づけると、n人目の选択肢ができるだけ多くなります... 二分という案数...答えに迫る
判定関数:
便宜上、X個のプレゼントが可能か否かを判断する際に、1からtm[1]の番号のプレゼントを 左半分の残りは右半分です
すなわちll_has=tm[1],rr_has=X-tm[1];
偶数の場合(なるべく左の)
ll[i]= min(tm[i],ll_has-ll[i-1])  //前の人はll[i-1]個を選んだが、残りはll_has-ll[i-1]オプション、できるだけ十分に選択
rr[i]=tm[i]-ll[i]    //すべて「左」で選択できない場合は、「右」で残りを選択するしかありません.
番号が奇数の場合(できるだけ右のものを持つ)
rr[i]=min(tm[i],rr_has-rr[i-1])   //前の人はrr[i-1]個を選んだが、残りはrr_has-rr[i-1]オプション、できるだけ十分
ll[i]=tm[i]-rr[i];  //同じ理屈で選ぶには左側で満タンに選ぶには足りない.
最後にn人目を見てみましょう 
最初に選んだプレゼントは1-tm[i]なので、この部分はすべて左の、、、つまりn番目の人は完全に左のを選ぶことができません
ll[n]=0の場合、現在の贈り物数Xは、n番目の人がすべて右側に選択できることを示し、すなわち、最初の人と衝突しない.
Xの下限はmax(tm[i]+tm[i+1])であるため だから隣の二人も必然的に衝突しない条件を満たすことができます!
この案は合法です!
主にn人目と1人目が衝突しているかどうかを判断することです

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std;
int min(int a,int b)
{return a<b?a:b;}
int tm[100005];
int ll[100005];
int rr[100005];
int n;
int main()
{
	int i,j;
	int ok(int);
	while(cin>>n&&n)
	{
		for (i=1;i<=n;i++)
		{
			scanf("%d",&tm[i]);
		}
		if (n==1)
		{
			printf("%d
",tm[1]);continue;  //spj
		}
		int maxx=0; 
		for (i=1;i<n;i++)
		{
			if (maxx<tm[i]+tm[i+1])
				maxx=tm[i]+tm[i+1];
		}
			if (maxx<tm[1]+tm[n])
	 		maxx=tm[1]+tm[n];
	
		int l=maxx;
		int r=100000*3;
		if (n%2)  //         maxx。       
		while(l<r)
		{
			if (r-l==1)
			{
				if (!ok(l))
				l=r;
				break;
			}
			int mid=(l+r)/2;
			if (ok(mid))
				r=mid;
			else
				l=mid+1;

		}
		printf("%d
",l);  

	}
	
	return 0;
}
 
int ok(int x)
{
	int i; 
	ll[1]=tm[1];
		rr[1]=0;
		int ll_has=ll[1];
		int rr_has=x-ll[1];
		for (i=2;i<=n;i++)
		{
			if (i%2==0)//       ，   n-1 （  ）   id        ，   n             
			{
				ll[i]=min(tm[i],ll_has-ll[i-1]); //            
				rr[i]=tm[i]-ll[i];			//        
			}
			else
			{
				rr[i]=min(tm[i],rr_has-rr[i-1]);
				ll[i]=tm[i]-rr[i];
			}
		}

		if (ll[n]==0)  
		return 1;
		return 0;
}