题意： n个人围成一圈，第i个人想要ri个不同的礼物，相邻的两个人礼物类型不能重复。
每种礼物不限量，求最少需要多少种礼物才行（1<=n<=100000）
训练指南， 37页。 分类讨论，n为偶数和奇数时。
n为偶数情况， p = max{r[i] + r[i + 1]} (1 <= i <= n) //记 r[n + 1] = r[1]
本题要点：
1、贪心来分析奇数情况
对应第一人，需要礼物 r[1], 用 r[1] 将 所有礼物分为两部分，
1 ~ r[1] 和 r[1] + 1 ~ p
int Left[MxaN]; //left[i] 表示第i个人 在 [1 ~ r1] 范围内取了多少个礼物
int Right[MxaN]; //right[i] 表示第i个人 在 [r1 + 1 ~ p] 范围内取了多少个礼物
假设第一个人 r[1] 个礼物全部取左边，也就是 left[1] = r[1], right[1] = 0;
后面的 人， i为奇数时候，尽量往右区间[r1 + 1 ~ p]取礼物，i为偶数时候，尽量往左[1 ~ r1]区间取礼物
如果最后能满足，left[n] == 0, 也就是 最后一人，取的礼物与 第一个人没有重复，说明 p 个礼物满足条件
2、二分查找 礼物总数 p， 找到最小的礼物总数
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MxaN = 100010;
int n;
int r[MxaN];
int Left[MxaN]; //left[i] 表示第i个人 在 [1 ~ r1] 范围内取了多少个礼物
int Right[MxaN]; //right[i] 表示第i个人 在 [r1 + 1 ~ p] 范围内取了多少个礼物//这里的p表示当前一共有多少个礼物
bool judge(int p)
{
int x = r[1], y = p - r[1];Left[1] = x, Right[1] = 0; //第一人，往左边取礼物for(int i = 2; i <= n; ++i){
if(i % 2 == 1) //i为奇数，往右边取{
Right[i] = min(y - Right[i - 1], r[i]); //每个人最多取 r[i]个礼物 Left[i] = r[i] - Right[i]; //另一边取的礼物数量}else{
//i为偶数，往左边取Left[i] = min(x - Left[i - 1], r[i]);Right[i] = r[i] - Left[i]; }}return Left[n] == 0;
}void solve()
{
if(1 == n){
printf("%d\n", r[1]);return;}r[n + 1] = r[1];int L = 0, R = 0; //L为 下限值，R 为上限值for(int i = 1; i <= n; ++i){
L = max(L, r[i] + r[i + 1]);}if(n % 2 == 1) //为奇数时{
for(int i = 1; i <= n; ++i){
R = max(R, 3 * r[i]);}while(L < R){
int M = (R + L) / 2;if(judge(M)){
R = M;}else{
L = M + 1; }}}printf("%d\n", L);
}int main()
{
while(scanf("%d", &n) == 1 && n){
for(int i = 1; i <= n; ++i){
scanf("%d", &r[i]);}solve();}return 0;
}/* 3 4 2 2 5 2 2 2 2 2 5 1 1 1 1 1 0 *//* 8 5 3 */