题干：
题目大意：
有n个人为成一个圈，其中第i个人想要r[i]种不同的礼物，相邻的两个人可以聊天，炫耀自己的礼物。如果两个相邻的人拥有同一种礼物，则双方都会很不高兴，问最少需要多少种不同的礼物才能满足所有人的需求，假设每种礼物有无限多个。 n<=100000
解题报告：
http://www.cnblogs.com/kickit/p/7619889.html
http://www.bubuko.com/infodetail-645767.html
总之就是偶数个的时候直接贪出相邻两者的最大值就可以。
奇数的时候：先单独安排第一个，并以这一个为分界线分为左右两个区域部分，然后剩下的分奇偶进行安排（第奇数个尽量往右安排，第偶数个尽量往左安排），然后安排到最后一个一定是尽量往右安排的，然后我们看这个是否和第一个有冲突就行了，如果没有冲突那一定是可以的，如果有冲突那一定就是说明我们用的李无数是不够的，因为我们这样一定是最优解了。
AC代码：
#include<cstdio>#include<iostream>#include<algorithm>#include<queue>#include<map>#include<vector>#include<set>#include<string>#include<cmath>#include<cstring>#define ll long long#define pb push_back#define pm make_pair#define fi first#define se secondusing namespace std;const int INF = 0x3f3f3f3f;const int MAX = 2e5 + 5;int a[MAX];int L[MAX],R[MAX];int n;bool ok(int x) {int l=a[1],r=x-a[1];L[1]=a[1];R[1]=0;for(int i = 2; i<=n; i++) {if(i%2==1) {R[i] = min(r-R[i-1],a[i]);L[i] = a[i]-R[i];}else {L[i] = min(l-L[i-1],a[i]);R[i] = a[i]-L[i];}}return L[n]==0;//填L[n]<=0也可以AC，，但是在这里还是==0比较好理解，因为L和R这两个数组都不存在为负情况。}int main(){while(~scanf("%d",&n)) {if(n == 0) break;int maxx = 0;for(int i = 1; i<=n; i++) {scanf("%d",a+i);maxx = max(maxx,a[i]+a[i-1]);}maxx = max(maxx,a[1]+a[n]);if(n == 1) {printf("%d\n",a[1]);continue;}else if(n % 2 == 0) {printf("%d\n",maxx);continue;}int l = maxx,r = INF;int mid = (l+r)>>1;while(l < r) {mid = (l+r)>>1;if(ok(mid)) r = mid;else l = mid+1;}printf("%d\n",l);}return 0 ;}
